各頂点に赤、黄、または緑に光る電球がある木が与えられます。以下の形式のクエリに多数答えてください：

• 1 v c — 頂点 $v$ の電球の色を色 $c$ に変更する。
• 2 v — 黄色に光っていることが保証された頂点 $v$ が与えられるので、木の中で $v$ を通る最短の信号機を見つけ、そこに含まれる辺の本数を出力する。信号機とは、木上の単純パスのうち、一方の端点が赤、もう一方の端点が緑であり、パスの内部頂点の少なくとも 1 つが黄色であるものとして定義される。

入力

入力の 1 行目には、テストケースの個数を表す整数 $t$ が与えられます（$1 \le t \le 2 \cdot 10^5$）。各テストケースについて：

1 行目には、木の頂点数とクエリの個数を表す 2 つの整数 $n$ と $q$ が与えられます（$1 \le n, q \le 2 \cdot 10^5$）。

続く $n - 1$ 行のそれぞれには、木の辺の両端点を表す整数の組 $u_i$ と $v_i$ が与えられます（$1 \le u_i, v_i \le n$; $u_i \ne v_i$）。これらの辺が木をなすことが保証されています。

次の行には、文字「R」、「Y」、「G」からなる長さ $n$ の文字列が与えられます。$i$ 番目の文字は $i$ 番目の頂点にある電球の初期の色を表します。「R」は赤色の光、「Y」は黄色、「G」は緑色を意味します。

その後、$q$ 個のクエリの記述が 1 行に 1 つずつ続きます：

• 1 v c — 頂点 $v$ の電球の色を色 $c$ に変更する（$1 \le v \le n$; $c \in \{\texttt{R}, \texttt{Y}, \texttt{G}\}$）。
• 2 v — $v$ を通る最短の信号機の長さを出力する（$1 \le v \le n$）。このクエリの時点で、頂点 $v$ の電球が黄色に光っていることが保証されています。また、この形式のクエリが少なくとも 1 つ存在することが保証されています。

すべてのテストケースにわたる $n$ の総和は $2 \cdot 10^5$ を超えないことが保証されています。すべてのテストケースにわたる $q$ の総和は $2 \cdot 10^5$ を超えないことが保証されています。

出力

各テストケースおよび形式 2 v の各クエリについて、赤色の頂点から始まり、黄色の頂点 $v$ を通り、緑色の頂点で終わる木上の最短単純パスに含まれる辺の本数を表す 1 つの数値 $d$ を出力してください。そのようなパスが存在しない場合は $-1$ を出力してください。

入出力例

入力例 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

出力例 1

2
2
3
-1

入力例 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

出力例 2

-1
2
-1
2
-1
-1
3