Bạn được cho một cây mà mỗi đỉnh có một bóng đèn phát sáng màu đỏ, vàng hoặc xanh lá. Hãy trả lời nhiều truy vấn thuộc các loại sau:

• 1 v c — đổi màu bóng đèn tại đỉnh $v$ thành màu $c$;
• 2 v — cho đỉnh $v$, được đảm bảo đang phát sáng màu vàng, hãy tìm đèn giao thông ngắn nhất trên cây đi qua $v$, và in ra số cạnh của nó. Một đèn giao thông được định nghĩa là một đường đi đơn trên cây có một đầu màu đỏ, đầu kia màu xanh lá, và ít nhất một trong các đỉnh bên trong của đường đi có màu vàng.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $t$, số lượng bộ dữ liệu ($1 \le t \le 2 \cdot 10^5$). Với mỗi bộ dữ liệu:

Dòng đầu tiên chứa hai số nguyên $n$ và $q$ — số lượng đỉnh của cây và số lượng truy vấn ($1 \le n, q \le 2 \cdot 10^5$).

Mỗi dòng trong $n - 1$ dòng tiếp theo chứa một cặp số nguyên $u_i$ và $v_i$ — hai đầu mút của một cạnh trên cây ($1 \le u_i, v_i \le n$; $u_i \ne v_i$). Dữ liệu đảm bảo các cạnh này tạo thành một cây.

Dòng tiếp theo chứa một xâu có độ dài $n$ gồm các chữ cái "R", "Y", "G", trong đó chữ cái thứ $i$ biểu thị màu ban đầu của bóng đèn tại đỉnh thứ $i$. "R" có nghĩa là đèn đỏ, "Y" — vàng, "G" — xanh lá.

Tiếp theo là mô tả của $q$ truy vấn, mỗi truy vấn trên một dòng:

• 1 v c — đổi màu bóng đèn tại đỉnh $v$ thành màu $c$ ($1 \le v \le n$; $c \in \{\texttt{R}, \texttt{Y}, \texttt{G}\}$);
• 2 v — in ra độ dài của đèn giao thông ngắn nhất đi qua $v$ ($1 \le v \le n$). Dữ liệu đảm bảo tại thời điểm thực hiện truy vấn này, bóng đèn tại đỉnh $v$ đang phát sáng màu vàng. Dữ liệu đảm bảo sẽ có ít nhất một truy vấn thuộc loại này.

Dữ liệu đảm bảo tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $2 \cdot 10^5$. Dữ liệu đảm bảo tổng của $q$ trong tất cả các bộ dữ liệu không vượt quá $2 \cdot 10^5$.

Kết quả

Với mỗi bộ dữ liệu và với mỗi truy vấn thuộc loại 2 v, hãy in ra một số duy nhất $d$ — số cạnh trên đường đi đơn ngắn nhất trong cây bắt đầu từ một đỉnh màu đỏ, đi qua đỉnh màu vàng $v$, và kết thúc tại một đỉnh màu xanh lá. Nếu không tồn tại đường đi như vậy, hãy in ra $-1$.

Ví dụ

Dữ liệu vào 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

Kết quả 1

2
2
3
-1

Dữ liệu vào 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

Kết quả 2

-1
2
-1
2
-1
-1
3