import java.util.*;

public class Verkko {
    private TreeSet<Integer> solmut;
    private TreeMap<Integer, TreeSet<Integer>> kaaret;

    public Verkko() {
        solmut = new TreeSet<Integer>();
        kaaret = new TreeMap<Integer, TreeSet<Integer>>();
    }

    public void lisaaSolmu(int solmu) {
        if (solmut.contains(solmu)) return;
        solmut.add(solmu);
        kaaret.put(solmu, new TreeSet<Integer>());
    }

    public void lisaaKaari(int alku, int loppu) {
        lisaaSolmu(alku);
        lisaaSolmu(loppu);
        kaaret.get(alku).add(loppu);
        kaaret.get(loppu).add(alku);
    }

    public void poistaKaari(int alku, int loppu) {
        kaaret.get(alku).remove(loppu);
        kaaret.get(loppu).remove(alku);
    }

    public TreeSet<Integer> haeSolmut() {
        return solmut;
    }

    public TreeSet<Integer> haeNaapurit(int solmu) {
        return kaaret.get(solmu);
    }

    private void syvyyshaku(int solmu, TreeSet<Integer> kaikki) {
        if (kaikki.contains(solmu)) return;
        kaikki.add(solmu);
        for (int naapuri : haeNaapurit(solmu)) {
            syvyyshaku(naapuri, kaikki);
        }
    }

    public boolean yhtenainen() {
        if (solmut.size() == 0) return true;
        TreeSet<Integer> solmutEkasta = new TreeSet<Integer>();
        syvyyshaku(solmut.first(), solmutEkasta);
        return (solmut.size() == solmutEkasta.size());
    }

    public boolean euler() {
        if (solmut.size() == 0) return true;
        TreeSet<Integer> solmutEkasta = new TreeSet<Integer>();
        for (int solmu : solmut) {
            if (haeNaapurit(solmu).size() == 0) continue;
            syvyyshaku(solmu, solmutEkasta);
            break;
        }
        for (int solmu : haeSolmut()) {
            TreeSet<Integer> naapurit = haeNaapurit(solmu);
            if (naapurit.size() % 2 == 1) return false;
            if (naapurit.size() > 0 &&
                !solmutEkasta.contains(solmu)) return false;
        }
        return true;
    }

    private boolean hamilton(int solmu, int alku, TreeSet<Integer> mukana) {
        if (mukana.contains(solmu)) return false;
        if (mukana.size()+1 == solmut.size()) {
            return haeNaapurit(solmu).contains(alku);
        }
        mukana.add(solmu);
        boolean kierros = false;
        for (int naapuri : haeNaapurit(solmu)) {
            kierros = kierros || hamilton(naapuri, alku, mukana);
            if (kierros) break;
        }
        mukana.remove(solmu);
        return kierros;
    }

    public boolean hamilton() {
        if (solmut.size() <= 1) return true;
        if (solmut.size() == 2) return false;
        return hamilton(solmut.first(), solmut.first(), new TreeSet<Integer>());
    }

    private ArrayList<Integer> haeAsteet() {
        ArrayList<Integer> asteet = new ArrayList<Integer>();
        for (int solmu : solmut) {
            asteet.add(haeNaapurit(solmu).size());
        }
        Collections.sort(asteet);
        return asteet;
    }

    private boolean isomorfinen(int[] omatSolmut, int kohta,
                                Verkko toinen,
                                TreeMap<Integer, Integer> kuvaus) {
        if (kohta == solmut.size()) {
            for (int solmu : omatSolmut) {
                TreeSet<Integer> toisenNaapurit =
                    toinen.haeNaapurit(kuvaus.get(solmu));
                if (haeNaapurit(solmu).size() !=
                    toisenNaapurit.size()) return false;
                for (int naapuri : haeNaapurit(solmu)) {
                    int toisenNaapuri = kuvaus.get(naapuri);
                    if (!toisenNaapurit.contains(toisenNaapuri)) return false;
                }
            }
            return true;
        }
        boolean tulos = false;
        for (int toisenSolmu : toinen.solmut) {
            if (kuvaus.containsValue(toisenSolmu)) continue;
            if (haeNaapurit(omatSolmut[kohta]).size() !=
                toinen.haeNaapurit(toisenSolmu).size()) continue;
            kuvaus.put(omatSolmut[kohta], toisenSolmu);
            tulos = tulos || isomorfinen(omatSolmut, kohta+1, toinen, kuvaus);
            kuvaus.remove(omatSolmut[kohta]);
            if (tulos) break;
        }
        return tulos;
    }

    public boolean isomorfinen(Verkko toinen) {
        if (solmut.size() != toinen.solmut.size()) return false;
        if (!haeAsteet().equals(toinen.haeAsteet())) return false;
        int[] omatSolmut = new int[solmut.size()];
        int kohta = 0;
        for (int solmu : solmut) {
            omatSolmut[kohta++] = solmu;
        }
        return isomorfinen(omatSolmut, 0, toinen,
                           new TreeMap<Integer, Integer>());
    }

    public Verkko teeKopio() {
        Verkko kopio = new Verkko();
        for (int solmu : solmut) {
            kopio.lisaaSolmu(solmu);
            for (int naapuri : haeNaapurit(solmu)) {
                kopio.lisaaKaari(solmu, naapuri);
            }
        }
        return kopio;
    }

    public String toString() {
        String kuvaus = "";
        for (int solmu : solmut) {
            kuvaus += solmu + ":";
            for (int naapuri : kaaret.get(solmu)) {
                kuvaus += " " + naapuri;
            }
            kuvaus += "\n";
        }
        return kuvaus;
    }
}