You are given a tree where each vertex has a light bulb that shines red, yellow, or green. Answer many queries of the following types:

• 1 v c — change the color of the light bulb at vertex $v$ to color $c$;
• 2 v — given vertex $v$, which is guaranteed to shine yellow, find the shortest traffic light in the tree that passes through $v$, and output the number of edges in it. A traffic light is defined as a simple path in the tree, one end of which is red, the other is green, and at least one of the internal vertices of the path is yellow.

Input

The first line of input contains an integer $t$, the number of test cases ($1 \le t \le 2 \cdot 10^5$). For each test case:

The first line contains two integers, $n$ and $q$ — the number of vertices in the tree and the number of queries ($1 \le n, q \le 2 \cdot 10^5$).

Each of the next $n - 1$ lines contains a pair of integers, $u_i$ and $v_i$ — the ends of an edge of the tree ($1 \le u_i, v_i \le n$; $u_i \ne v_i$). It is guaranteed that these edges form a tree.

The following line contains a string of length $n$ consisting of the letters "R", "Y", "G", where the $i$-th letter denotes the initial color of the light bulb at the $i$-th vertex. "R" means red light, "Y" — yellow, "G" — green.

Then follow the descriptions of $q$ queries, one per line:

• 1 v c — change the color of the light bulb at vertex $v$ to color $c$ ($1 \le v \le n$; $c \in \{\texttt{R}, \texttt{Y}, \texttt{G}\}$);
• 2 v — output the length of the shortest traffic light passing through $v$ ($1 \le v \le n$). It is guaranteed that at the time of this query, the light bulb at vertex $v$ shines yellow. It is guaranteed that there will be at least one query of this type.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$. It is guaranteed that the sum of $q$ across all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case and for each query of the type 2 v, output a single number $d$ — the number of edges on the shortest simple path in the tree that starts at a red vertex, passes through the yellow vertex $v$, and ends at a green vertex. If such paths do not exist, output $-1$.

Examples

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