import java.util.*;

public class Hamilton {
    public static boolean valmis;

    public static void teeKierros(Verkko verkko, LinkedList<Integer> kierros) {
        if (valmis) return;
        if (verkko.haeSolmut().size() == kierros.size()) {
            if (verkko.haeNaapurit(kierros.getFirst()).contains(kierros.getLast())) {
                valmis = true;
                for (int solmu : kierros) {
                    System.out.print(solmu + " ");
                }
                System.out.println(kierros.getFirst());
            }
        }
        for (int uusi : verkko.haeNaapurit(kierros.getLast())) {
            if (kierros.contains(uusi)) continue;
            kierros.addLast(uusi);
            teeKierros(verkko, kierros);
            kierros.removeLast();
        }
    }

    public static void teeHamilton(Verkko verkko) {
        if (verkko.haeSolmut().size() == 0) return;
        int alku = verkko.haeSolmut().first();
        LinkedList<Integer> kierros = new LinkedList<Integer>();
        kierros.addLast(alku);
        valmis = false;
        teeKierros(verkko, kierros);
        if (!valmis) {
            System.out.println("Verkossa ei ole Hamiltonin kierrosta!");
        }
    }

    public static void main(String[] args) {
        Verkko verkko = new Verkko();
        verkko.lisaaKaari(1, 4);
        verkko.lisaaKaari(2, 4);
        verkko.lisaaKaari(2, 5);
        verkko.lisaaKaari(4, 5);
        verkko.lisaaKaari(1, 3);
        verkko.lisaaKaari(3, 4);
        verkko.lisaaKaari(1, 2);
        teeHamilton(verkko);
    }
}