import java.util.HashSet;
import java.util.Iterator;

public class Papirlenke implements Iterable<String> {

    Papir foerste, siste;
    int antall = 0;

    protected class Papir {
        String farge = "";
        Papir neste, under = null;
        Papir[] nabopapir = new Papir[2];

        public void fargelegg(String farge) {
            this.farge = farge;
        }

        public String farge() {
            return farge;
        }

        public void settNeste(Papir p) {
            neste = p;
            nabopapir[0] = neste;
        }

        public void settUnder(Papir p) {
            under = p;
            nabopapir[1] = under;
        }

        public Papir hentNeste() {
            return neste;
        }

        public Papir hentUnder() {
            return under;
        }

        public Papir[] hentNabopapir() {
            return nabopapir;
        }
    }

    public int antall() {
        return antall;
    }

    public void leggTilNeste() {
        Papir nytt = new Papir();

        if (antall == 0) {
            foerste = siste = nytt;
        }

        else {
            if (siste.hentUnder() == null) {
                leggTilUnder();
            }
            else {
                siste.settNeste(nytt);
                siste = nytt;
            }
        }
        antall++;
    }

    public void leggTilUnder() {
        if (antall > 0) {
            Papir nytt = new Papir();
            siste.settUnder(nytt);
            antall++;
        }
    }

    public void fargeleggAlle(String farge1, String farge2) { // DFS
        Papir peker = foerste;
        HashSet<Papir> fargelagt = new HashSet<>();

        fargeleggLenka(fargelagt, peker, farge1, farge2);
    }

    // DFS-visit
    public void fargeleggLenka(HashSet<Papir> fargelagt, Papir peker, String farge1, String farge2) {
        
        if (peker != null && !fargelagt.contains(peker)) {
            peker.fargelegg(farge1);

            fargelagt.add(peker);

            for (Papir papir : peker.hentNabopapir()) {
                fargeleggLenka(fargelagt, papir, farge2, farge1);
            }
        }
    }

    @Override
    public Iterator<String> iterator() {
        return new PapirIterator();
    }

    public class PapirIterator implements Iterator<String> {
        private Papir peker = foerste;

        @Override
        public boolean hasNext() {
            return peker != null;
        }

        @Override
        public String next() {
            String farger = peker.farge();
            if (peker.hentUnder() != null) {
                farger += "\n     " + peker.hentUnder().farge();
            }
            peker = peker.hentNeste();
            return farger;

        }
    }
    
}