Description

给定一棵树，其顶点关联着一些颜色，以及一个对该树的操作命令序列。命令要么是更新操作，要么是查询操作。每个更新操作会改变指定顶点的颜色，而不改变树的结构。每个查询会询问树中包含所有指定颜色顶点的最小连通子图中的边数。

你的任务是假设命令按给定顺序执行，找出每个查询的答案。

Input Format

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

$$\begin{aligned} & n \\ & a_1 \; b_1 \\ & \vdots \\ & a_{n-1} \; b_{n-1} \\ & c_1 \; \ldots \; c_n \\ & m \\ & command_1 \\ & \vdots \\ & command_m \end{aligned}$$

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

$$\text{U} \; x_k \; y_k$$

或

$$\text{Q} \; y_k$$

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

Output Format

对于每个查询，输出树中包含所有指定颜色顶点的最小连通子图中的边数。如果树中不包含任何具有指定颜色的顶点，则输出 $-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

2
2
0
-1
3
2
2
0