Problem D
Colorful Trees

Given a tree with colored vertices, for each edge, how many pairs of vertices with the same color have that edge on the path between them? Note that since it’s a tree, each pair of nodes has exactly one path between them.

Input

The first line of input contains a single integer $n$ ($2 \le n \le 10^5$), which is the number of nodes in the tree. The nodes are numbered from $1$ to $n$.

Each of the next $n$ lines contains a single integer $c$ ($1 \le c \le n$). These are the colors of the nodes, in order.

Each of the next $n-1$ lines contains two integers $a$ and $b$ ($1 \le a < b \le n$), denoting an undirected edge from node $a$ to node $b$.

Output

Output $n-1$ lines. On each line, output a single integer, which is the number of pairs of vertices with the same color that have that edge on the path between them. Output these answers for the edges in the order that they appear in the input.

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

2
2
3
2
3

4
2
2
2
2
3 4
2 4
1 2

3
4
3