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 .
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 .
Print lines, where the line contains a single integer denoting .
5 1 2 3 2 3 1 2 2 3 2 4 1 5
10 9 11 9 12
The Sample Input defines the following tree:
Each is calculated as follows: