畀定一棵樹，每個頂點上面都有一個燈膽，會發紅光、黃光或者綠光。請回答多個以下類型嘅查詢：

• 1 v c —— 將頂點 $v$ 嘅燈膽顏色改為顏色 $c$；
• 2 v —— 畀定頂點 $v$（保證當時發緊黃光），搵出樹入面經過 $v$ 嘅最短紅綠燈，並輸出入面包含嘅邊數。紅綠燈定義為樹入面嘅一條簡單路徑，其中一端係紅色，另一端係綠色，而且路徑嘅內部頂點入面至少有一個係黃色。

輸入格式

輸入嘅第一行包含一個整數 $t$，代表測試用例嘅數量（$1 \le t \le 2 \cdot 10^5$）。對於每個測試用例：

第一行包含兩個整數 $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$）。保證呢啲邊構成一棵樹。

下一行包含一個長度為 $n$、由字母「R」、「Y」、「G」組成嘅字串，其中第 $i$ 個字母代表第 $i$ 個頂點上面燈膽嘅初始顏色。「R」代表紅燈，「Y」代表黃燈，「G」代表綠燈。

跟住係 $q$ 個查詢嘅描述，每行一個：

• 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$ 嘅燈膽係發緊黃光嘅。保證至少有一個呢種類型嘅查詢。

保證所有測試用例入面 $n$ 嘅總和唔超過 $2 \cdot 10^5$。保證所有測試用例入面 $q$ 嘅總和唔超過 $2 \cdot 10^5$。

輸出格式

對於每個測試用例同埋每個類型為 2 v 嘅查詢，輸出一個數字 $d$ —— 樹入面由紅色頂點開始、經過黃色頂點 $v$、並喺綠色頂點結束嘅最短簡單路徑上面嘅邊數。如果唔存在噉樣嘅路徑，請輸出 $-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