3. Tristo

Na motívy filmu Tristo vymyslel Buj počítačovú hru. Ako za chvíľu iste pochopíte, prešla komplikovaným a dlhým vývojom. Jej hlavné herné mechaniky si priblížime nižšie.

V tejto hre hráč ovláda zhruba tristo dážďoviek. Tie žijú vo svojom podzemnom komplexe, ktorý vyzerá ako graf-strom. Vrcholy stromu reprezentujú miesta v podzemnom komplexe, pričom koreň stromu reprezentuje východ z komplexu.

Každá dážďovka v komplexe okupuje nejaký súvislý úsek vrcholov – teda vrcholy, na ktorých sa nachádza niektorý článok dážďovky, tvoria cestu. Koncovým článkom dážďovky budeme hovoriť hlava a chvost.

Úlohou hráča je riadiť evakuáciu dážďoviek von z komplexu. Dážďovky sú pripravené – aj preto je každá dážďovka otočená hlavou smerom ku koreňu stromu. To znamená, že spomedzi všetkých jej článkov je jej hlava ku koreňu najbližšie.

Hra prebieha v ťahoch. V každom ťahu hráč klikne na niektorú dážďovku, a tá sa pohne o toľko smerom ku koreňu, o koľko sa dá. Nevie sa samozrejme pohnúť do vrcholu, ktorý už je obsadený článkom inej dážďovky. Takisto sa dážďovka nevie natiahnuť – dĺžka dážďovky zostane po vykonaní ťahu rovnaká. Ak po vykonaní ťahu hlava dážďovky dosiahne koreň stromu, dážďovka je zachránená a komplex opúšťa.

No a vašou úlohou bude túto hernú mechaniku čo najefektívnejšie implementovať.

Úloha

Dostanete popis podzemného komplexu. Následne dostanete popis niekoľkých hier, ktoré sa všetky odohrávajú v tomto komplexe.

Popis hry pozostáva z rozmiestnenia dážďoviek v ňom, a postupnosti ťahov hráča. Každý ťah určuje jednu dážďovku, na ktorú hráč klikol. Pre každý hráčov ťah zistite, v ktorých vrcholoch sa bude nachádzať hlava a chvost určenej dážďovky po tom, čo sa ťah vykoná.

Formát vstupu

Na prvom riadku vstupu je jedno celé číslo \(n\) – počet vrcholov stromu.

Nasleduje riadok s \(n\) celými číslami \(p_1, p_2, \ldots, p_n\), pričom susedné čísla sú oddelené práve jednou medzerou. Ak \(p_i = 0\), tak vrchol \(i\) je koreňom stromu. V opačnom prípade je otcom vrcholu \(i\) vrchol \(p_i\).

Nasleduje prázdny riadok, a po ňom riadok s jedným celým číslom \(t\) – počet hier. Nasledujú popisy týchto hier.

Popis hry začína prázdnym riadkom. Za ním nasleduje riadok s jedným celým číslom \(m\) – počet dážďoviek. Nasleduje \(m\) riadkov, a v každom z nich sú dve celé čísla oddelené medzerou – čísla vrcholov, v ktorých sa nachádza hlava a chvost dážďovky.

V ďalšom riadku je jedno celé číslo \(q\) – počet ťahov hráča. Nasledovný riadok obsahuje \(q\) celých čísel \(d_1, d_2, \ldots, d_q\), pričom susedné čísla sú oddelené práve jednou medzerou. \(i\)-te z týchto čísel je poradové číslo dážďovky, na ktorú hráč v \(i\)-tom ťahu klikol.

Obmedzenia

• \(t \leq 1\,000\)
• Celkový počet vrcholov, celkový počet dážďoviek ani celkový počet ťahov nepresiahne \(100\,000\).
• Pre každú dážďovku platí, že vrchol, v ktorom sa nachádza hlava je predkom vrcholu, v ktorom sa nachádza chvost.

Formát výstupu

Pre každý ťah vypíšte na samostatný riadok dve čísla \(h\) a \(c\) oddelené jednou medzerou – čísla vrcholov, v ktorých sa nachádzajú hlava a chvost dážďovky po vykonaní ťahu.

Ak dážďovka komplex opustí, vypíšte namiesto toho saved, a v prípade, že sa dážďovka v komplexe už nenachádza, vypíšte illegal.

Príklady

Input:

14
0 1 1 2 2 2 3 3 5 5 7 10 11 11

2

6
1 2
6 6
9 9
10 12
3 8
13 13
11
6 5 4 1 5 6 3 2 4 3 1

3
1 12
7 14
3 8
6
3 2 1 2 3 2

Output:

7 7
3 8
5 10
saved
saved
saved
9 9
saved
saved
saved
illegal
3 8
7 14
saved
7 14
saved
saved