Codah ClubVježbaj. Pošalji. Napreduj.
Prijavi se
Hrvatski
#000155

z-red

Mali Z gleda u stablo sa N vrhova indeksiranih od 1 do N, koji na pocetku mogu biti obojani u crvenu ili zelenu boju, a mogu ju i mjenjati tijekom vremena. Z-a povremeno zanima koji je k-ti crveni vrh na putu od vrha 1 do vrha v. Kako je ovo tezak posao za njega zeli da vi simulirate stablo kroz Q operacija zadanih u jednom od sljedeca 2 oblika:


1 k v - ispisi indeks k-tog crvenog vrha na putu od vrha 1 do vrha v( ukljucujuci vrhove 1 i v )


2 v - promjeni boju vrha v, iz crvene u zelenu i obratno


InputU prvoj liniji standardnog ulaza nalaze se cijeli brojevi N ( 2 <= N <= 50000 ) i Q ( 1 <= Q <= 150000 ). U sljedecoj liniji nalazi se niz od N znakova koji predstavljaju pocetno stanje stabla, tocnije, ako je i-ti znak niza 0 znaci da je vrh i na pocetku obojan u crveno, ako je i-ti znak niza 1 znaci da je obojan u zeleno.

U sljedecih N-1 linija nalaze se po 2 cijela broja a i b ( 1 <= a < b <= N ), koji oznacavaju postojecu vezu u stablu izmedju vrhova a i b. Od svakog vrha u stablu preko zadanih veza postojati ce tocno jedan put do svakog drugog vrha.

U sljedecih Q linija nalazi se po 2 ili 3 cijela broja, ovisno o operaciji. Ako je prvi broj u liniji 1 iza njega slijede 2 cijela broja k ( 1 <= k <= N ) i v ( 1 <= v <= N ), a ako je prvi broj u liniji 2 iza njega slijedi cijeli broj v ( 1 <= v <= N ).


OutputNa standardni izlaz za svaku naredbu tipa 1 ispisati odgovarajuci indeks vrha, a ako on ne postoji ispisati -1.

Ulaz: 5 3
10101
1 2
1 3
1 5
2 4
1 2 4
2 4
1 2 4
Izlaz: 4
-1

Ulaz: 8 7
00000000
1 2
8 1
2 3
4 2
7 3
5 3
8 6
1 3 5
2 3
1 3 5
1 3 6
2 1
1 3 4
1 2 4
Izlaz:3
5
6
-1
4

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.