給你一棵樹，每個頂點上都有一顆燈泡，會發出紅光、黃光或綠光。請回答多次以下類型的查詢：

• 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