Fişierul intrare/ieşire:pandemie.in, pandemie.outSursăFMI No Stress 9
AutorUsurelu Florian RobertAdăugată defminostress9FMI No Stress 9 •fminostress9
Timp execuţie pe test0.25 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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. 

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. 

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.

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.

Exemplu

pandemie.inpandemie.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
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?