== 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 isi pune Q intrebari 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 intrebarii, iar $S$ reprentand statul asupra caruia este supusa intrebarea.
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
* PROPUN sa dam 4 teste pe N^2, 4 teste pe Nloglog si 2 teste cu Nlog. Bagam N maxim 100k si ajustam timpii
* $1 ≤ N, Q ≤ 50.000$
* Pentru $20$ de puncte (testele $1-2$), $1 ≤ N, Q ≤ 1000$
* Pentru alte $30$ de puncte (testele $3-4-5$), $1 ≤ N, Q ≤ 10.000$
* Daca 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 ≤ 100.000$.
* Pentru $50$ de puncte (testele $1-2-3-4-5$), $1 ≤ N, Q ≤ 1000$.
* **Se garanteaza ca nu se va pleca niciodata dintr-un sat virusat**.
* Se garanteaza ca muchiile **bidirectionale** citite formeaza un **arbore cu radacina in 1**.
h2. Exemplu
