Du får ett träd där varje hörn har en glödlampa som lyser rött, gult eller grönt. Besvara många frågor av följande typer:

• 1 v c — ändra färgen på glödlampan i hörn $v$ till färgen $c$;
• 2 v — givet hörnet $v$, som garanterat lyser gult, hitta det kortaste trafikljuset i trädet som passerar genom $v$, och skriv ut antalet kanter i det. Ett trafikljus definieras som en enkel väg i trädet vars ena ände är röd, den andra är grön, och minst ett av de inre hörnen på vägen är gult.

Indata

Den första raden i indatan innehåller ett heltal $t$, antalet testfall ($1 \le t \le 2 \cdot 10^5$). För varje testfall:

Den första raden innehåller två heltal, $n$ och $q$ — antalet hörn i trädet och antalet frågor ($1 \le n, q \le 2 \cdot 10^5$).

Var och en av de följande $n - 1$ raderna innehåller ett par heltal, $u_i$ och $v_i$ — ändpunkterna för en kant i trädet ($1 \le u_i, v_i \le n$; $u_i \ne v_i$). Det garanteras att dessa kanter bildar ett träd.

Följande rad innehåller en sträng av längd $n$ bestående av bokstäverna "R", "Y", "G", där den $i$-te bokstaven anger den ursprungliga färgen på glödlampan i det $i$-te hörnet. "R" betyder rött ljus, "Y" — gult, "G" — grönt.

Därefter följer beskrivningarna av $q$ frågor, en per rad:

• 1 v c — ändra färgen på glödlampan i hörn $v$ till färgen $c$ ($1 \le v \le n$; $c \in \{\texttt{R}, \texttt{Y}, \texttt{G}\}$);
• 2 v — skriv ut längden på det kortaste trafikljuset som passerar genom $v$ ($1 \le v \le n$). Det garanteras att glödlampan i hörn $v$ lyser gult vid tidpunkten för denna fråga. Det garanteras att det finns minst en fråga av denna typ.

Det garanteras att summan av $n$ över alla testfall inte överstiger $2 \cdot 10^5$. Det garanteras att summan av $q$ över alla testfall inte överstiger $2 \cdot 10^5$.

Utdata

För varje testfall och för varje fråga av typen 2 v, skriv ut ett enda tal $d$ — antalet kanter på den kortaste enkla vägen i trädet som börjar i ett rött hörn, passerar genom det gula hörnet $v$ och slutar i ett grönt hörn. Om sådana vägar inte existerar, skriv ut $-1$.

Exempel

Indata 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

Utdata 1

2
2
3
-1

Indata 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

Utdata 2

-1
2
-1
2
-1
-1
3