说明

给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。每个顶点 $i$ 被赋予一种颜色 $c_i$。

你需要处理 $Q$ 个询问。在每个询问中，会给出四个整数 $u_1, v_1, u_2, v_2$。

对于每个询问，确定最大的整数 $K$（$0 \leq K \leq N$），使得以下条件成立：

• 对于每个 $j = 1, 2, \ldots, K$，从 $u_1$ 到 $v_1$ 的路径上颜色为 $j$ 的顶点数量，等于从 $u_2$ 到 $v_2$ 的路径上颜色为 $j$ 的顶点数量。

输入格式

输入格式如下：

$$\begin{aligned} & N \\ & a_1 \ b_1 \\ & a_2 \ b_2 \\ & \vdots \\ & a_{N-1} \ b_{N-1} \\ & c_1 \ c_2 \ \ldots \ c_N \\ & Q \\ & \text{Query}_1 \\ & \text{Query}_2 \\ & \vdots \\ & \text{Query}_Q \end{aligned}$$

每个询问的格式如下：

$$u_1 \ v_1 \ u_2 \ v_2$$

• $1 \leq N \leq 100\,000$
• $1 \leq a_i, b_i \leq N$ ($1 \leq i \leq N - 1$)
• $1 \leq c_i \leq N$ ($1 \leq i \leq N$)
• $1 \leq Q \leq 100\,000$
• $1 \leq u_1, v_1, u_2, v_2 \leq N$ ($1 \leq i \leq Q$)
• 给定的图是一棵树。
• 所有输入值均为整数。

输出格式

输出 $Q$ 行。在第 $i$ 行（$1 \leq i \leq Q$），输出第 $i$ 个询问的答案。

6
2 3
4 3
6 2
3 5
2 1
1 2 2 3 1 1
4
1 6 5 4
6 5 1 5
1 1 6 6
1 5 4 2

0
6
6
0