树是一个连通（任意两个顶点之间都存在路径）、无向（图的边没有方向）、无环（没有环）的图。 彩色树是指每个顶点都有特定颜色的树。 “冗长路径”（tedious path）是指树中起点和终点颜色相同，且路径中没有重复顶点或边的路径。注意，路径中中间顶点的颜色（如果有的话）无关紧要。

给定一棵有 $N$ 个顶点的彩色树，你的任务是计算对于每一条边，经过该边的冗长路径的数量。

输入格式

第一行包含顶点数 $N$ ($1 \le N \le 10^5$)。第二行包含 $N$ 个整数 $C_1, \dots, C_N$，其中 $C_i$ ($1 \le C_i \le N$) 表示顶点 $i$ 的颜色。接下来的 $N - 1$ 行，每行包含两个整数 $u$ 和 $v$，表示一条边（$1 \le u, v \le N$ 且 $u \neq v$）。保证给定的图是一棵树。

输出格式

输出 $N - 1$ 个整数，表示经过每一条边的冗长路径数量，顺序与输入中给出的边顺序一致。

样例

输入样例 1

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

输出样例 1

4 3 3 4 1

输入样例 2

12
1 2 3 1 2 2 1 3 2 3 1 2
1 2
2 3
2 4
4 5
4 6
1 7
7 8
7 9
9 10
6 11
6 12

输出样例 2

10 2 10 4 9 9 2 6 2 3 4