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:

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

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

* 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

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

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

1 1
1 3
3 6

3 5

3 3

2 3
3 3
| 1
  2

  2

  3

  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") ==