Ti viene dato un albero in cui ogni vertice ha una lampadina che brilla di luce rossa, gialla o verde. Rispondi a molte query dei seguenti tipi:

• 1 v c — cambia il colore della lampadina nel vertice $v$ nel colore $c$;
• 2 v — dato il vertice $v$, che è garantito brillare di giallo, trova il semaforo più corto nell'albero che passa per $v$ e stampa il numero di archi in esso contenuti. Un semaforo è definito come un cammino semplice nell'albero, un'estremità del quale è rossa, l'altra è verde, e almeno uno dei vertici interni del cammino è giallo.

Input

La prima riga dell'input contiene un intero $t$, il numero di casi di test ($1 \le t \le 2 \cdot 10^5$). Per ciascun caso di test:

La prima riga contiene due interi, $n$ e $q$ — il numero di vertici nell'albero e il numero di query ($1 \le n, q \le 2 \cdot 10^5$).

Ciascuna delle successive $n - 1$ righe contiene una coppia di interi, $u_i$ e $v_i$ — gli estremi di un arco dell'albero ($1 \le u_i, v_i \le n$; $u_i \ne v_i$). È garantito che questi archi formino un albero.

La riga seguente contiene una stringa di lunghezza $n$ composta dalle lettere "R", "Y", "G", dove l'$i$-esima lettera indica il colore iniziale della lampadina nell'$i$-esimo vertice. "R" significa luce rossa, "Y" — gialla, "G" — verde.

Seguono poi le descrizioni di $q$ query, una per riga:

• 1 v c — cambia il colore della lampadina nel vertice $v$ nel colore $c$ ($1 \le v \le n$; $c \in \{\texttt{R}, \texttt{Y}, \texttt{G}\}$);
• 2 v — stampa la lunghezza del semaforo più corto che passa per $v$ ($1 \le v \le n$). È garantito che al momento di questa query la lampadina nel vertice $v$ brilli di giallo. È garantito che ci sarà almeno una query di questo tipo.

È garantito che la somma di $n$ su tutti i casi di test non superi $2 \cdot 10^5$. È garantito che la somma di $q$ su tutti i casi di test non superi $2 \cdot 10^5$.

Output

Per ciascun caso di test e per ciascuna query del tipo 2 v, stampa un singolo numero $d$ — il numero di archi sul cammino semplice più corto nell'albero che inizia in un vertice rosso, passa per il vertice giallo $v$ e termina in un vertice verde. Se tali cammini non esistono, stampa $-1$.

Esempi

Input 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

Output 1

2
2
3
-1

Input 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

Output 2

-1
2
-1
2
-1
-1
3