Colorful Trees

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