import java.util.ArrayList;

class Graf{
    class Node {
        ArrayList<Node> naboer;
        boolean harVaert;
        int id;

        public Node(int id) {
            naboer = new ArrayList<Node>();
            harVaert = false;
            this.id = id;
        }

        public void printNaboer() {
            for (Node nabo : naboer) {
                System.out.println(nabo.id);
            }
        }
    }

    ArrayList<Node> noder = new ArrayList<Node>();

    public void printKanter() {
        for (Node node : noder) {
            System.out.println("Node : " + node.id);
            node.printNaboer();
            System.out.println("\n");
        }
    }

    public void settInnNode(int id) {
        Node ny = new Node(id);
        noder.add(ny);
    }

    public void leggTilKant(int fraId, int tilId) {
        Node fra = finnNode(fraId);
        Node til = finnNode(tilId);

        if (fra == null || til == null) {
            System.out.println("Forsoker aa legge til kant mellom ikke-eksisterende noder.");
            return;
        }

        fra.naboer.add(til);
    }

    public void finnesVei(int idFra, int idTil) {
        tilbakestillHarVaert();

        Node current = finnNode(idFra);
        finnesVei(idTil, current);
    }

    private void finnesVei(int idTil, Node current) {
        current.harVaert = true;

        if (current.id == idTil) {
            System.out.println("Utvei funnet!");
            return;
        }

        for (Node nabo : current.naboer) {
            if (!nabo.harVaert) {
                finnesVei(idTil, nabo);
            }
        }
    }

    private Node finnNode(int id) {
        for (Node node : noder) {
            if (node.id == id) {
                return node;
            }
        }
        return null;
    }

    private void tilbakestillHarVaert() {
        for (Node node : noder) {
            node.harVaert = false;
        }
    }
}