import java.util.ArrayList;

class Skog {
    private final int ANTKRYSS, ANTSTIER;
    private Kryss[] kryssene;

    public Skog(int antk, int ants) {
        ANTKRYSS = antk;
        ANTSTIER = ants;
        kryssene = new Kryss[ANTKRYSS];

        for (int i = 0; i < ANTKRYSS; i++) {
            kryssene[i] = new Kryss();
        }

        for (int i = 0; i < ANTSTIER; i++) {
            Kryss start = hentTilfeldigKryss();
            Kryss slutt = hentTilfeldigKryss();

            int lengde = Trekk.trekkInt(220, 2500);
            int utsiktsVerdi = Trekk.trekkInt(1, 6);
            Sti ny;
            int typeSti = Trekk.trekkInt(0, 3);

            if (typeSti == 0) { // Kjerrevei
                ny = new Kjerrevei(lengde, start, slutt);
            } else if (typeSti == 1) { // Natursti 
                ny = new Natursti(lengde, start, slutt);
            } else if (typeSti == 2) {
                ny = new KjerreveiMedUtsikt(lengde, start, slutt, utsiktsVerdi);
            } else {
                ny = new NaturstiMedUtsikt(lengde, start, slutt, utsiktsVerdi);
            }

            start.leggTilSti(ny);
            slutt.leggTilSti(ny);
        }
    }

    public Kryss hentTilfeldigKryss() {
        int indeks = Trekk.trekkInt(0, ANTKRYSS - 1);
        return kryssene[indeks];
    }

    public Kryss hentTilfeldigStart() {
        boolean fantEgnetStart = false;
        
        // Ingen uendelige løkke, ettersom oppgaveteksten sier at det finnes minst en 
        // sti som ikke er isolert
        while (! fantEgnetStart) {
            Kryss tilfeldigStart = hentTilfeldigKryss();
            if (! tilfeldigStart.erIsolert()) {
                // fantEgnetStart = true;
                return tilfeldigStart;
            }
        }
        return null;
    }
}

class Kryss {
    private ArrayList<Sti> motendeStier = new ArrayList<>();

    public Sti hentTilfeldigSti() {
        if (motendeStier.size() == 0)
            return null;

        int indeks = Trekk.trekkInt(0, motendeStier.size() - 1);
        return motendeStier.get(indeks);
    }

    public boolean erIsolert() {
        return motendeStier.isEmpty();
    }

    public void leggTilSti(Sti ny) {
        motendeStier.add(ny);
    }

    // @Override
    // public boolean equals(Object annen) {
    //     if (! (annen instanceof Kryss))
    //         return false;
        
    //     if (this.navn.equals(annen.navn) && this.antallStier == annen.antallStier) 
    //         return true;
    //     return false;
    // }
}

abstract class Sti {
    protected int lengde;
    protected Kryss start, slutt;

    public Sti(int leng, Kryss sta, Kryss slu) {
        lengde = leng;
        start = sta;
        slutt = slu;
    }

    public Kryss finnAndreEnde(Kryss endepunkt) {
        if (endepunkt.equals(start))
            return slutt;
        
        else if (endepunkt.equals(slutt)) 
            return start;

        // Fikk ikke inn et gyldig endepunkt
        return null;
    }

    public int beregnGaaTid(int fart) {
        return lengde / fart;
    }
}

class Natursti extends Sti {

    public Natursti(int lengde, Kryss start, Kryss slutt) {
        super(lengde, start, slutt);
    }
}

class Kjerrevei extends Sti {

    public Kjerrevei(int lengde, Kryss start, Kryss slutt) {
        super(lengde, start, slutt);
    }
}

class KjerreveiMedUtsikt extends Kjerrevei implements GodUtsikt {
    private int utsiktsVerdi;

    public KjerreveiMedUtsikt(int lengde, Kryss start, Kryss slutt, int utsikt) {
        super(lengde, start, slutt);
        if (utsiktsVerdi < 1 || utsiktsVerdi > 6) {
            throw new UgyldigUtsiktsVerdi(utsiktsVerdi + "");
        }
        utsiktsVerdi = utsikt;
    }

    @Override
    public int hentUtsiktsVerdi() {
        return utsiktsVerdi;
    }
}

class NaturstiMedUtsikt extends Natursti implements GodUtsikt {
    private int utsiktsVerdi;

    public NaturstiMedUtsikt(int lengde, Kryss start, Kryss slutt, int utsikt) {
        super(lengde, start, slutt);
        if (utsiktsVerdi < 1 || utsiktsVerdi > 6) {
            throw new UgyldigUtsiktsVerdi(utsiktsVerdi + "");
        }
        utsiktsVerdi = utsikt;
    }

    @Override
    public int hentUtsiktsVerdi() {
        return utsiktsVerdi;
    }
}

class UgyldigUtsiktsVerdi extends RuntimeException {

    public UgyldigUtsiktsVerdi(String feil) {
        super(feil);
    }
}

interface GodUtsikt {
    int hentUtsiktsVerdi();
}

class Trekk {
    public static int trekkInt(int min, int max) {
        return (int) (Math.random()*(max - min + 1)) + min;
    }
}