Zadanie
Fajné planty
Počet bodov: 40
Merlin so svojím jedným kopčekom zmrzliny natešene hopsal po meste. Ponorený do rozkoše skackal okolo parku, keď náhle uprel zrak a prudko zastal, sánka mu takmer o zem buchla a oči z jamiek vyskočili. V Bratislave sa konalo bienále Konfrontácia Symetrických Plantov. Každému botanikovi nabehne husia koža iba pri predstave tých nádherných stromčekov z celého sveta. Dnešok už hádam nemôže byť lepší.
Merlin vošiel na výstavu a obdivoval dreviny. Po chvíli započul nervóznu debatu. Jeden z členov poroty ochorel a nie je schopný posudzovať symetrickosť stromov. Vyhodnotenie sa má konať už o pár hodín a ak sa nenájde náhradník, tak sa všetko zruší. Merlin sa okamžite ponúkol, že to zvládne, načo ho pochopiteľne všetci vysmiali. Ako druhý pokus sa ponúkol, že naprogramuje algoritmus, ktorý objektívne posúdi symetrickosť stromov. Merlin od pohľadu vyzerá ako špičkový programátor, takže jeho ponuku prijali. Čo ale od pohľadu nebolo vidno, je, že Merlinovi sa za chrbtom topila zmrzlina a kompletne mu zašpinila všetky prsty.
Úloha
Merlin algoritmus kvôli špinavým rukám nemôže napísať a tak sa obracia na vás. Na posúdenie dostanete zakorenený strom a pre každý jeho vrchol jeho deti v poradí zľava doprava. Vašou úlohou bude určiť, či je symetrický alebo nie. Teda či ide o ten istý strom keď by sme ho prevrátili podľa stredovej osi.
Vstup a Výstup
Prvý riadok vstupu obsahuje číslo \(n (1 \leq n \leq 2\cdot 10^5)\), ktoré označuje počet vrcholov stromu. Nasleduje \(n\) riadkov. Na \(i\)-tom riadku je \(k_i + 1\) medzerou oddelených čísel. Prvé číslo bude \(k_i\), ktoré udáva počet detí vrcholu \(i\). Zvyšných \(k_i\) čísel sú čísla vrcholov jeho detí v poradí zľava doprava. Koreň má vždy číslo 0 a indexujeme od 0.
Vypíšte jeden riadok s textom ^_^, ak je strom symetrický, inak O_o.
Príklad
Input:
9
3 1 2 3
2 4 5
1 6
2 7 8
0
0
0
0
0Output:
^_^Input:
13
3 1 2 3
0
3 4 5 6
0
2 7 8
0
2 9 10
0
1 11
1 12
0
0
0Output:
^_^Input:
13
3 1 2 3
0
3 4 6 5
0
2 7 8
0
2 9 10
0
1 11
1 12
0
0
0Output:
O_o