Bobo 有一棵包含 $n$ 个顶点的树，顶点编号为 $1, 2, \dots, n$，共有 $(n - 1)$ 条边。 第 $i$ 个顶点的颜色为 $c_i$，第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。

令 $C(x, y)$ 表示在删除边 $(x, y)$ 后，以 $x$ 为根的子树中所有顶点的颜色集合。

对于所有的 $1 \leq i \leq (n - 1)$，Bobo 想知道 $R_i$，即 $C(a_i, b_i)$ 与 $C(b_i, a_i)$ 的交集大小（即 $|C(a_i, b_i) \cap C(b_i, a_i)|$）。

输入格式

输入包含最多 15 组数据。对于每组数据：

第一行包含一个整数 $n$ ($2 \leq n \leq 10^5$)。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($1 \leq c_i \leq n$)。

接下来的 $(n - 1)$ 行中，第 $i$ 行包含两个整数 $a_i, b_i$ ($1 \leq a_i, b_i \leq n$)。

输出格式

对于每组数据，输出 $(n - 1)$ 个整数 $R_1, R_2, \dots, R_{n - 1}$。

样例

样例输入 1

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

样例输出 1

1
2
1
1
1
2
1