Stāsts

Kādā datorfirmā $N$ datori ir saslēgti vienotā tīklā tā, ka katru divu datoru pāris ir vai nu tieši savienots ar kabeli, vai arī eksistē unikāla secīgu datoru virkne no viena datora līdz otram, kur katrus divus blakus datorus savieno kabelis. Datori tīklā ir sanumurēti ar naturāliem skaitļiem no $1$ līdz $N$ pēc kārtas.

Viena šāda datortīkla piemērs parādīts 1. attēlā.

Meistars Matīss ir pamanījis, ka datortīkls vairs nedarbojas kā nākas, un pēc viņa ilggadējās iepriekšējās pieredzes ir skaidrs, ka vainīgs ir kāds no sistēmā esošajiem kabeļiem.

Meistara rīcībā ir līdzekļi, kas ļauj pieslēgties jebkuriem diviem datoriem un noteikt, vai starp tos savienojošiem kabeļiem kāds nav bojāts.

Uzrakstiet datorprogrammu, kas organizē šādu pieslēgšanos virkni ar mērķi atrast bojāto kabeli.

Komunikācija

Šis ir interaktīvs uzdevums. Jūsu programmai, sākot darbu, pirmajā ievaddatu rindā dots naturāls skaitlis $N$ ($2 \leq N \leq 20000$) - datoru skaits datortīklā. Nākamajās $N-1$ ievaddatu rindās katrā dots viena tieši ar kabeli savienota datoru pāra apraksts - savienoto datoru numuri, kas atdalīti ar tukšumzīmi.

Bojātā kabeļa atrašanās vietu vērtēšanas sistēma tur slepenībā.

Tad jūsu programma var veikt vaicājumus, tos rakstot izvadā šādā formātā: $0\ d_1\ d_2$, kur $d_1$ un $d_2$ ir divu datoru numuri - atšķirīgi naturāli skaitļi ($1 \leq d_1,\ d_2 \leq N$).

Vērtēšanas sistēma uz vaicājumu izdod atbildi nākamajā ievaddatu rindā. Atbilde ir vesels skaitlis - $0$, ja kabeļu virknē no $d_1$ līdz $d_2$ kāds no kabeļiem ir bojāts, vai $1$, ja neviens no kabeļiem šajā virknē nav bojāts.

Jūsu programma katrā testā var veikt ne vairāk kā $20000$ vaicājumus.

Kad bojātā kabeļa atrašanās vieta noteikta, programmai jāizvada $1\ d_x\ d_y$ ($1 \leq d_x,\ d_y \leq N$), kur $d_x$ un $d_y$ ir bojātā kabeļa galos esošo datoru numuri, un darbība jābeidz. Vērtēšanas sistēma neatbildēs uz šo izvadu un nepieņems sekojošus vaicājumus.

Raksturojot kabeli, galapunktu secībai nav nozīmes. Visos testos būs tieši viens bojātais kabelis.

Piemērs

8
2 5
8 7
4 2
1 8
3 6
3 7
8 2

0 1 6

1

0 7 5

1

1 4 2

Izpildes resursu ierobežojumi

Apakšuzdevumi un to vērtēšana

Piezīmes

Lai garantētu, ka jūsu programmas "vaicājumus" saņem vērtēšanas sistēma, jums ir "jāsinhronizē" ( flush ) izvaddatu plūsma ( stdout ) pēc katra vaicājuma.

Ja testa ietvaros tiks pārsniegts maksimāli atļautais vaicājumu skaits, tā statuss pēc testēšanas būs "Nepareiza atbilde".