给定一棵树，其顶点关联着颜色，并给出一系列操作。操作分为更新操作和查询操作。每次更新操作会改变指定顶点的颜色，而不改变树的结构。每次查询操作询问包含所有指定颜色的顶点的最小连通子图中的边数。

假设操作按给定顺序执行，你的任务是求出每次查询的答案。

输入格式

输入包含单个测试用例，格式如下：

$n$ $a_1 \ b_1$ $\vdots$ $a_{n-1} \ b_{n-1}$ $c_1 \ \dots \ c_n$ $m$ $command_1$ $\vdots$ $command_m$

第一行包含一个整数 $n$ ($2 \le n \le 100\,000$)，表示树的顶点数。顶点编号为 $1$ 到 $n$。接下来的 $n-1$ 行，每行包含两个整数 $a_i$ ($1 \le a_i \le n$) 和 $b_i$ ($1 \le b_i \le n$)，表示第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。保证所有顶点连通，即给定的图是一棵树。下一行包含 $n$ 个整数 $c_1$ 到 $c_n$，其中 $c_j$ ($1 \le c_j \le 100\,000$) 是顶点 $j$ 的初始颜色。下一行包含一个整数 $m$ ($1 \le m \le 100\,000$)，表示操作的数量。接下来的 $m$ 行，每行包含一个操作，格式如下：

U $x_k \ y_k$ 或 Q $y_k$

当第 $k$ 个操作以 U 开头时，表示一个更新操作，将顶点 $x_k$ ($1 \le x_k \le n$) 的颜色更改为 $y_k$ ($1 \le y_k \le 100\,000$)。当第 $k$ 个操作以 Q 开头时，表示一个查询操作，询问包含所有颜色为 $y_k$ ($1 \le y_k \le 100\,000$) 的顶点的最小连通子图中的边数。

输出格式

对于每个查询，输出包含所有指定颜色顶点的最小连通子图中的边数。如果树中不包含任何该颜色的顶点，则输出 $-1$。

样例

输入 1

5
1 2
2 3
3 4
2 5
1 2 1 2 3
11
Q 1
Q 2
Q 3
Q 4
U 5 1
Q 1
U 3 2
Q 1
Q 2
U 5 4
Q 1

输出 1

2
2
0
-1
3
2
2
0