== include(page="template/taskheader" task_id="pandemie") ==
Omenirea se confrunta cu o grava pandemie la nivel global din cauza virusului mielenevirus. Din aceasta pricina, Organizatia Entuziasta Internationala a Spitalelor (OEIS), a hotarat stabilirea unui centru medical in cel mai avansat stat, iGorj. Cele N state (numerotate de la 1 la N, iGorj fiind statul nr 1) la nivel mondial se pot reprezenta cu tot cu legaturile bidirectionale dintre ele sub forma unui arbore. Mielenevirusul este foarte imprevizibil: oamenii dintr-un stat X se pot vindeca instant sau se pot imbolnavi toti spontan. Vladuri isi pune Q intrebari de forma: 1 X (al X-lea stat este virusat), 2 X (al X-lea stat este vindecat) si 3 X (daca s-ar afla in al X-lea stat, care ar fi cel mai apropiat stat de iGorj, la care ar putea ajunge daca nu ar trece prin niciun stat virusat.
Ajutati-l pe Vladuri sa afle pentru fiecare intrebare de tipul 3, statul cu pricina.
Omenirea se confrunta cu o grava pandemie la nivel global din cauza virusului mielenevirus. Din aceasta pricina, Organizatia Entuziasta Internationala a Spitalelor (OEIS), a hotarat stabilirea unui centru medical in cel mai avansat stat, iGorj. Cele N state (numerotate de la 1 la N, iGorj fiind statul nr 1) la nivel mondial se pot reprezenta cu tot cu legaturile bidirectionale dintre ele sub forma unui arbore. Mielenevirusul este foarte imprevizibil: oamenii dintr-un stat X se pot vindeca instant sau se pot imbolnavi toti spontan. Vladuri are de rezolvat Q operatii de forma:
* $1 X$ - al $X$-lea stat este virusat
* $2 X$ - al $X$-lea stat este vindecat
* $3 X$ - daca s-ar afla in al $X$-lea stat, care ar fi cel mai apropiat stat de iGorj, la care ar putea ajunge daca nu ar trece prin niciun stat virusat?
Ajutati-l pe Vladuri sa afle pentru fiecare intrebare de tipul $3$ statul cu pricina.
h2. Date de intrare
Fişierul de intrare $pandemie.in$ va contine pe prima linie un numar N, iar pe urmatoarele N-1 linii cate 2 numere A si B reprezentand faptul ca exista o legatura intre al A-lea stat si al B-lea stat. Pe urmatoarea linie va contine un numar Q reprezentand numarul de intrebari de tipurile 1, 2 si 3 pe care si le va pune Vladuri. Pe urmatoarele Q linii se vor afla cate 2 numere O si S, O reprezentand tipul intrebarii, iar S reprentand statul asupra caruia este supusa intrebarea.
Fişierul de intrare $pandemie.in$ va contine:
* Pe prima linie un numar $N$ cu semnificatia din enunt.
* Pe urmatoarele $N - 1$ linii cate doua numere $A$ si $B$, reprezentand un drum **bidirectional** intre al $A$-lea stat si al $B$-lea stat.
* Pe urmatoarea linie se afla un numar $Q$ reprezentand numarul de intrebari.
* Pe urmatoarele $Q$ linii se vor afla cate doua numere $Op$ si $S$, $Op$ reprezentand tipul operatiei, iar $S$ reprentand statul asupra caruia se aplica operatia.
h2. Date de ieşire
În fişierul de ieşire $pandemie.out$ se vor afla pe cate o linie distincta, cate un numar reprezentand raspunsul pentru fiecare intrebare de tipul 3.
În fişierul de ieşire $pandemie.out$ se vor afla pe cate o linie distincta, cate un numar reprezentand raspunsul pentru fiecare intrebare de tipul $3$.
h2. Restricţii
* $1 ≤ N, Q ≤ 300.000$
* Pentru 40 de puncte, $1 ≤ N, Q ≤ 2.000$
* Pentru alte 40 de puncte, $1 ≤ N, Q ≤ 100.000$
* Daca nu pentru o intrebare de tip 3, nu se poate pleca din nodul X inspre iGorj, se va afisa X.
* Se neglijeaza starea nodului X (virusat/ nevirusat) la intrebarile de tip 3.
* $1 ≤ N, Q ≤ 120.000$.
* Pentru $40$ de puncte, $1 ≤ N, Q ≤ 3000$.
* Pentru alte $40$ de puncte, $1 ≤ N, Q ≤ 50.000$.
* **Se garanteaza ca nu se va pleca niciodata dintr-un stat virusat**.
* Se garanteaza ca muchiile **bidirectionale** citite formeaza un **arbore cu radacina in 1**.
h2. Exemplu
table(example). |_. pandemie.in |_. pandemie.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 7
1 2
1 3
2 4
2 6
2 7
4 5
7
3 5
1 1
1 3
3 6
3 5
2 3
3 3
| 1
2
2
3
|
| 10
1 2
1 3
1 7
9 7
10 9
2 8
2 4
5 8
3 6
11
3 10
3 5
1 1
3 8
1 8
3 5
2 8
3 5
1 3
2 3
3 3
| 1
1
2
5
2
3
|
== include(page="template/taskfooter" task_id="pandemie") ==
