Ker je vseh dreves na listih na njegovi pisalni mizi občutno preveč, da bi v nekaj dnevih uspel poiskati pravega, te je prosil za pomoč. Zelo bi mu pomagal že s tem, če bi iz množice podatkov o drevesih izbral le takšne, ki bi lahko predstavljali levo poravnano dvojiško drevo.
Poduk: Levo poravnano dvojiško drevo je polno drevo, ki mu morda manjkajo nekateri listi na desni strani v spodnjem nivoju (glej sliko).
![Slika](http://putka.upm.si/tasks/2015/2015_poskusno/drevesa?att=Completetree001.png)
Vhodni podatki
Prva vrstica vhodne datoteke vsebuje eno samo število n, tj. število testnih primerov. V prvi vrstici vsakega primera je število vozlišč dvojiškega drevesa m, nato pa sledi za vsako vozlišče po ena vrstica, ki vsebuje dve števili: [math] in [math]. Število [math] predstavlja enolično oznako vozlišča, število [math] pa oznako njegovega starša. Če je vozlišče [math] koren drevesa, je [math] enak −1. Podatki zagotovo predstavljajo neko dvojiško drevo.
Omejitve vhodnih podatkov
- n ≤ 100
- m ≤ 100000
- 0 ≤ [math] ≤ 100000
- −1 ≤ b ≤ 100000
Izhodni podatki
Za vsak testni primer izpiši po eno številko (vsako v svoji vrstici):
1, če podatki lahko predstavljajo levo poravnano dvojiško drevo in 0 sicer.
Primer vhoda
Koda: Izberi vse
3
3
5 3
3 -1
7 3
3
1 -1
3 1
7 3
9
1 -1
2 1
3 1
4 2
5 2
6 3
7 3
8 4
9 7
Pripadajoč izhod
Koda: Izberi vse
1
0
0