Pandemie

pandemie

== 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 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.

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), 0 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.

h2. Date de intrare

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.

Fişierul de intrare $pandemie.in$ ...

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$ ...

h2. Restricţii

* $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 |

| 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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

| 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
|

h3. Explicaţie
...

== include(page="template/taskfooter" task_id="pandemie") ==