On vous donne un arbre dont chaque sommet possède une ampoule qui brille en rouge, jaune ou vert. Répondez à plusieurs requêtes des types suivants :

• 1 v c — changer la couleur de l'ampoule au sommet $v$ en la couleur $c$ ;
• 2 v — étant donné le sommet $v$, dont il est garanti qu'il brille en jaune, trouver le plus court feu de circulation dans l'arbre qui passe par $v$, et afficher le nombre d'arêtes qu'il contient. Un feu de circulation est défini comme un chemin simple dans l'arbre dont une extrémité est rouge, l'autre est verte, et dont au moins l'un des sommets internes est jaune.

Entrée

La première ligne de l'entrée contient un entier $t$, le nombre de cas de test ($1 \le t \le 2 \cdot 10^5$). Pour chaque cas de test :

La première ligne contient deux entiers, $n$ et $q$ — le nombre de sommets dans l'arbre et le nombre de requêtes ($1 \le n, q \le 2 \cdot 10^5$).

Chacune des $n - 1$ lignes suivantes contient une paire d'entiers, $u_i$ et $v_i$ — les extrémités d'une arête de l'arbre ($1 \le u_i, v_i \le n$ ; $u_i \ne v_i$). Il est garanti que ces arêtes forment un arbre.

La ligne suivante contient une chaîne de longueur $n$ composée des lettres « R », « Y », « G », où la $i$-ème lettre désigne la couleur initiale de l'ampoule au $i$-ème sommet. « R » signifie lumière rouge, « Y » — jaune, « G » — verte.

Suivent ensuite les descriptions de $q$ requêtes, une par ligne :

• 1 v c — changer la couleur de l'ampoule au sommet $v$ en la couleur $c$ ($1 \le v \le n$ ; $c \in \{\texttt{R}, \texttt{Y}, \texttt{G}\}$) ;
• 2 v — afficher la longueur du plus court feu de circulation passant par $v$ ($1 \le v \le n$). Il est garanti qu'au moment de cette requête, l'ampoule au sommet $v$ brille en jaune. Il est garanti qu'il y aura au moins une requête de ce type.

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $2 \cdot 10^5$. Il est garanti que la somme de $q$ sur tous les cas de test ne dépasse pas $2 \cdot 10^5$.

Sortie

Pour chaque cas de test et pour chaque requête du type 2 v, affichez un seul nombre $d$ — le nombre d'arêtes sur le plus court chemin simple dans l'arbre qui commence à un sommet rouge, passe par le sommet jaune $v$ et se termine à un sommet vert. Si de tels chemins n'existent pas, affichez $-1$.

Exemples

Entrée 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

Sortie 1

2
2
3
-1

Entrée 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

Sortie 2

-1
2
-1
2
-1
-1
3