Coloured Mountain Hut

You are in charge of $N$ huts and the roads that connect them. Each hut has a number from $1$ to $N$. There are $N-1$ paths in total. All paths are the same length and can be taken in either direction. Also, from any hut, you can reach any other hut by going through some of the paths.

All the huts are painted with a color to mark them. Every hut has at least one other hut that is the same color as it, so that climbers can move between huts of the same color. For each hut, you are trying to find the hut that can be reached in the shortest travel distance among the other huts of the same color as that hut.

You are given the color of the hut and information about the paths that connect the huts directly to each other. Write a program that, for each hut, find the hut with the shortest travel distance among the other huts of the same color as the hut, and outputs the shortest travel distance. The length of the path is assumed to be 1 for all.

Input

The input is given in the following format.

$N$
$c_1$
$c_2$
:
$c_N$
$s_1$ $t_1$
$s_2$ $t_2$
:
$s_{N-1}$ $t_{N-1}$

In the first line, the number of huts $N$ ($2 \leq N \leq 200,000$) is given. In the following $N$ lines, the color of the $i$-th hut $c_i$ ($1 \leq c_i \leq N$) is given in integers. In the following $N-1$ lines, the information of the path directly connecting the two huts is given. $s_i$ and $t_i$ ($1 \leq s_i < t_i \leq N$) are the numbers of the two huts connected by the $i$-th path. For any two huts, there should be no more than one path that directly connects them.

Output

The output consists of $N$ lines. For hut $i$, find the hut with the shortest travel distance among the other huts of the same color, and output the shortest travel distance in line $i$.

Sample Input and Output

Sample Input

8
1
2
3
3
2
2
3
1
1 2
1 3
2 4
2 5
4 6
5 7
7 8

Sample Output

4
1
3
3
1
2
3
4

---