You are given an unrooted tree of nodes numbered from to . Each node has a color, .
Let be the number of different colors in the path between node and node . For each node , calculate the value of , defined as follows:
Your task is to print the value of for each node .
Input Format
The first line contains a single integer, , denoting the number of nodes.
The second line contains space-separated integers, , where each describes the color of node .
Each of the subsequent lines contains space-separated integers, and , defining an undirected edge between nodes and .
Constraints
Output Format
Print lines, where the line contains a single integer denoting .
Sample Input
5
1 2 3 2 3
1 2
2 3
2 4
1 5
Sample Output
10
9
11
9
12
Explanation
The Sample Input defines the following tree:
Each is calculated as follows: