| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 7 | 7 | 3 | 100.000% |
Veenusel on hierarhiline haldusjaotus: planeet on jagatud regioonideks, iga regioon võib olla jagatud alamregioonideks, iga alamregiooon omakorda alam-alamregioonideks j.n.e. Kokku on planeedil $N$ haldusüksust, mis on nummerdatud 1ドル \ldots N,ドル kusjuures haldusüksus number 1ドル$ on terve planeet. Seega moodustab Veenuse haldusjaotus puu, mille juurtipu tähis on 1ドル$.
Veenusel on ka palju vulkaane ja selle elanikud on pidevas mures võimalike pursete pärast. Sellepärast on igas haldusüksuses spetsiaalne vulkaanilise aktiivsuse tagajärgedega võitlemise keskus. Keskus aktiveerub, kui üksuses kuulutatakse välja kõrge ohutase. Huvitaval kombel on võimalik, et mingis haldusüksuses on ohutase kõrge, kuigi kõigis selle alamüksustes on ohutase madal.
Kui korraga on aktiivsed mitu vulkaanilise aktiivsuse tagajärgedega võitlemise keskust, tuleb nende tegevust koordineerida. Selleks määratakse olukorda juhtima kõige väiksem haldusüksus, mis sisaldab kõiki kõrge ohutasemega haldusüksusi. Iga haldusüksus loetakse kõigist oma alam\-üksustest rangelt suuremaks, isegi kui tal on ainult üks alamüksus.
Vulkaaniline aktiivsus on väga muutuv, sellepärast on vaja programmi, mis saab teateid selle kohta, kui mõnes haldusüksuses on ohutase muutunud madalast kõrgeks või kõrgest madalaks, ja leiab iga sellise teate järel, milline haldusüksus nüüd olukorda juhtima peaks.
Sisendi esimesel real on Veenuse haldusüksuste arv $N$ (1ドル \le N \le 10^5$).
Järgmisel $N$ real on igaühel ühe haldusüksuse kirjeldus. Real number 1ドル + i$ on kõigepealt haldusüksuse $i$ alamüksuste arv $K_i$ (0ドル \le K_i \le N - 1$) ja selle järel $K_i$ täisarvu $A_{i,j}$ (1ドル \le A_{i,j} \le N$), mis näitavad, et haldusüksused $A_{i,1}, A_{i,2}, \ldots, A_{i,K_i}$ on üksuse $i$ alamüksused.
Järgmisel real on teadete arv $Q$ (1ドル \le Q \le 10^5$).
Selle järel järgmisel $Q$ real on igaühel ühe teate kirjeldus: täisarvud $T_i$ ja $V_i$ (1ドル \le T_i \le 2,ドル 1ドル \le V_i \le N$), kust $T_i = 1$ tähendab, et haldusüksuses $V_i$ muutus ohutase madalast kõrgeks, ja $T_i = 2,ドル et üksuse $V_i$ ohutase muutus kõrgest madalaks.
Võib eeldada, et alguses on kõigi haldusüksuste ohutase madal ja et sisendandmed on kooskõlalised (kui mingi üksuse kohta tuleb ohutaseme kõrgeks muutumise teade, siis enne oli selle üksuse ohutase madal, ja vastupidi).
Väljastada täpselt $Q$ rida, igale reale üks täisarv. Väjundi reale $i$ väljastada sisendi real $N + 2 + i$ kirjeldatud teate järel olukorda juhtiva haldusüksuse number. Kui kõigis haldusüksustes on ohutase madal, väljastada arv 0ドル$.
7 2 2 3 2 4 5 2 6 7 0 0 0 0 10 1 1 2 1 1 4 1 5 1 6 1 7 2 5 2 4 2 7 1 3
1 0 4 2 1 1 1 3 6 3
Selle näite haldusüksuste struktuur on kujutatud joonisel ja teated on järgmised:
4 1 2 1 4 0 1 3 4 1 4 1 3 1 1 2 1
4 4 1 4
Pange tähele, et selles näites on mõnel haldusüksusel ainult üks alamüksus.
5 4 2 3 4 5 0 0 0 0 6 1 2 1 3 2 2 1 5 1 2 2 5
2 1 3 1 1 1