Se te da un árbol donde cada vértice tiene una bombilla que brilla en rojo, amarillo o verde. Responde a muchas consultas de los siguientes tipos:

• 1 v c — cambiar el color de la bombilla en el vértice $v$ al color $c$;
• 2 v — dado el vértice $v$, el cual se garantiza que brilla en amarillo, encontrar el semáforo más corto en el árbol que pasa por $v$, e imprimir el número de aristas en él. Un semáforo se define como un camino simple en el árbol, uno de cuyos extremos es rojo, el otro es verde, y al menos uno de los vértices internos del camino es amarillo.

Entrada

La primera línea de la entrada contiene un entero $t$, el número de casos de prueba ($1 \le t \le 2 \cdot 10^5$). Para cada caso de prueba:

La primera línea contiene dos enteros, $n$ y $q$ — el número de vértices en el árbol y el número de consultas ($1 \le n, q \le 2 \cdot 10^5$).

Cada una de las siguientes $n - 1$ líneas contiene un par de enteros, $u_i$ y $v_i$ — los extremos de una arista del árbol ($1 \le u_i, v_i \le n$; $u_i \ne v_i$). Se garantiza que estas aristas forman un árbol.

La siguiente línea contiene una cadena de longitud $n$ compuesta por las letras "R", "Y", "G", donde la $i$-ésima letra indica el color inicial de la bombilla en el $i$-ésimo vértice. "R" significa luz roja, "Y" — amarilla, "G" — verde.

Luego siguen las descripciones de $q$ consultas, una por línea:

• 1 v c — cambiar el color de la bombilla en el vértice $v$ al color $c$ ($1 \le v \le n$; $c \in \{\texttt{R}, \texttt{Y}, \texttt{G}\}$);
• 2 v — imprimir la longitud del semáforo más corto que pasa por $v$ ($1 \le v \le n$). Se garantiza que en el momento de esta consulta, la bombilla en el vértice $v$ brilla en amarillo. Se garantiza que habrá al menos una consulta de este tipo.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $2 \cdot 10^5$. Se garantiza que la suma de $q$ en todos los casos de prueba no supera $2 \cdot 10^5$.

Salida

Para cada caso de prueba y para cada consulta del tipo 2 v, imprime un solo número $d$ — el número de aristas en el camino simple más corto en el árbol que comienza en un vértice rojo, pasa por el vértice amarillo $v$ y termina en un vértice verde. Si no existen tales caminos, imprime $-1$.

Ejemplos

Entrada 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

Salida 1

2
2
3
-1

Entrada 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

Salida 2

-1
2
-1
2
-1
-1
3