Alice si Bob, doi renumiti montaniarzi care tocmai au iesit din sesiune, s-au hotarat sa isi petreaca vacanta in inima muntilor. Intr-o zi, explorand padurile din preajma, au descoperit o pestera despre care au presupus ca odinioara a apartinut unei colonii de maimute. Conform cunostintelor acumulate in domeniu, pestera este formata din $N$ camere unite prin coridoare bidirectionale astfel incat intre oricare doua camere exista un singur drum. Mai mult, peretii fiecarei camere au fost vopsiti de catre maimute intr-o culoare notata cu un numar intreg intre $1$ si $N$.
Temerarii nostri doresc sa reconstituie harta pesterii. Pentru aceasta ei procedeaza in felul urmator:

* initial Bob se afla in camera $#1$
* cand Bob intra intr-o camera isi noteaza culoarea camerei respective. Apoi isi alege cel mai din stanga coridor pe care nu l-a vizitat si intra in camera adiacenta (evident, nevizitata anterior). Daca nu exista

* initial Bob se afla in camera $#1$ tinand mana stanga lipita de perete
* la fiecare pas, Bob isi noteaza culoarea camerei in care se afla, apoi - tinandu-si permanent mana stanga lipita de perete - intra intr-o noua camera (care putea sa mai fi fost vizitata sau nu)
* Bob se opreste cand ajunge din nou in camera $#1$ iar toate cele N camere au fost vizitate

 
Bob intra in camera #1 si isi noteaza culoarea camerei respective. Apoi isi alege cel mai din stanga coridor pe care nu l-a vizitat, intra in noua camera, isi noteaza culoarea camerei respective

h2. Date de intrare