Sinulle annetaan puu, jonka jokaisessa solmussa on hehkulamppu, joka loistaa punaisena, keltaisena tai vihreänä. Vastaa lukuisiin seuraavan tyyppisiin kyselyihin:

• 1 v c — vaihda solmun $v$ hehkulampun väriksi väri $c$;
• 2 v — annetaan solmu $v$, jonka taataan loistavan keltaisena; etsi puusta lyhin solmun $v$ kautta kulkeva liikennevalo ja tulosta sen kaarien lukumäärä. Liikennevalo määritellään puun yksinkertaiseksi poluksi, jonka toinen pää on punainen, toinen pää on vihreä ja vähintään yksi polun sisäsolmuista on keltainen.

Syöte

Syötteen ensimmäinen rivi sisältää kokonaisluvun $t$, testitapausten lukumäärän ($1 \le t \le 2 \cdot 10^5$). Jokaiselle testitapaukselle:

Ensimmäinen rivi sisältää kaksi kokonaislukua, $n$ ja $q$ — puun solmujen lukumäärän ja kyselyjen lukumäärän ($1 \le n, q \le 2 \cdot 10^5$).

Jokainen seuraavista $n - 1$ rivistä sisältää kokonaislukuparin $u_i$ ja $v_i$ — puun kaaren päätepisteet ($1 \le u_i, v_i \le n$; $u_i \ne v_i$). On taattu, että nämä kaaret muodostavat puun.

Seuraava rivi sisältää pituutta $n$ olevan merkkijonon, joka koostuu kirjaimista "R", "Y", "G", missä $i$-s kirjain ilmaisee $i$-nnessä solmussa olevan hehkulampun alkuperäisen värin. "R" tarkoittaa punaista valoa, "Y" — keltaista, "G" — vihreää.

Tämän jälkeen seuraa $q$ kyselyn kuvaukset, yksi kullakin rivillä:

• 1 v c — vaihda solmun $v$ hehkulampun väriksi väri $c$ ($1 \le v \le n$; $c \in \{\texttt{R}, \texttt{Y}, \texttt{G}\}$);
• 2 v — tulosta lyhimmän solmun $v$ kautta kulkevan liikennevalon pituus ($1 \le v \le n$). On taattu, että tämän kyselyn hetkellä solmun $v$ hehkulamppu loistaa keltaisena. On taattu, että tällaisia kyselyjä on vähintään yksi.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $2 \cdot 10^5$. On taattu, että lukujen $q$ summa yli kaikkien testitapausten ei ylitä arvoa $2 \cdot 10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle ja jokaiselle tyyppiä 2 v olevalle kyselylle yksi luku $d$ — kaarien lukumäärä puun lyhimmällä yksinkertaisella polulla, joka alkaa punaisesta solmusta, kulkee keltaisen solmun $v$ kautta ja päättyy vihreään solmuun. Jos tällaisia polkuja ei ole olemassa, tulosta $-1$.

Esimerkit

Syöte 1

1
7 7
1 2
2 3
2 4
4 5
4 6
6 7
RYGYRGY
2 2
1 7 G
2 4
1 1 Y
2 2
1 5 Y
2 4

Tuloste 1

2
2
3
-1

Syöte 2

3
3 2
1 2
2 3
YRG
2 1
1 1 Y
4 3
1 2
2 3
2 4
RYGY
2 2
1 1 Y
2 4
5 8
1 2
2 3
3 4
3 5
YRYGY
2 3
1 5 G
2 1
1 2 Y
2 3
1 1 R
2 3
1 4 Y

Tuloste 2

-1
2
-1
2
-1
-1
3