Du får gitt et tre der hver node har en lyspære som lyser rødt, gult eller grønt. Svar på mange spørringer av følgende typer:

• 1 v c — endre fargen på lyspæren i node $v$ til fargen $c$;
• 2 v — gitt noden $v$, som garantert lyser gult, finn det korteste trafikklyset i treet som går gjennom $v$, og skriv ut antallet kanter i det. Et trafikklys er definert som en enkel sti i treet der den ene enden er rød, den andre er grønn, og minst én av de indre nodene på stien er gul.

Inndata

Den første linjen i inndataene inneholder et heltall $t$, antallet testtilfeller ($1 \le t \le 2 \cdot 10^5$). For hvert testtilfelle:

Den første linjen inneholder to heltall, $n$ og $q$ — antallet noder i treet og antallet spørringer ($1 \le n, q \le 2 \cdot 10^5$).

Hver av de neste $n - 1$ linjene inneholder et par med heltall, $u_i$ og $v_i$ — endepunktene til en kant i treet ($1 \le u_i, v_i \le n$; $u_i \ne v_i$). Det er garantert at disse kantene danner et tre.

Den påfølgende linjen inneholder en streng med lengde $n$ bestående av bokstavene «R», «Y», «G», der den $i$-te bokstaven angir den opprinnelige fargen på lyspæren i den $i$-te noden. «R» betyr rødt lys, «Y» — gult, «G» — grønt.

Deretter følger beskrivelsene av $q$ spørringer, én per linje:

• 1 v c — endre fargen på lyspæren i node $v$ til fargen $c$ ($1 \le v \le n$; $c \in \{\texttt{R}, \texttt{Y}, \texttt{G}\}$);
• 2 v — skriv ut lengden på det korteste trafikklyset som går gjennom $v$ ($1 \le v \le n$). Det er garantert at lyspæren i node $v$ lyser gult på tidspunktet for denne spørringen. Det er garantert at det vil være minst én spørring av denne typen.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $2 \cdot 10^5$. Det er garantert at summen av $q$ over alle testtilfeller ikke overstiger $2 \cdot 10^5$.

Utdata

For hvert testtilfelle og for hver spørring av typen 2 v, skriv ut et enkelt tall $d$ — antallet kanter på den korteste enkle stien i treet som starter i en rød node, går gjennom den gule noden $v$ og slutter i en grønn node. Hvis slike stier ikke finnes, skriv ut $-1$.

Eksempler

Inndata 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

Inndata 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