给你一棵树，每个顶点上都有一盏灯泡，灯泡可以亮起红灯、黄灯或绿灯。你需要回答以下两种类型的多次查询：

• 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 \{\text{R}, \text{Y}, \text{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
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

输出样例 1

2
2
3
-1
-1
2
-1
2
-1
-1
3