Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | pandemie.in, pandemie.out | Sursă | FMI No Stress 9 |
| Autor | Usurelu Florian Robert | Adăugată de |  FMI No Stress 9 •fminostress9 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 32768 kbytes |
| Scorul tău | N/A | Dificultate | N/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 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.
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 intrebarii, iar S reprentand statul asupra caruia este supusa intrebarea.
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.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 |
