Bobo has a tree with $n$ vertices numbered by $1, 2, \dots, n$ and $(n - 1)$ edges. The $i$-th vertex has color $c_i$, and the $i$-th edge connects vertices $a_i$ and $b_i$.
Let $C(x, y)$ denotes the set of colors in subtree rooted at vertex $x$ deleting edge $(x, y)$.
Bobo would like to know $R_i$ which is the size of intersection of $C(a_i, b_i)$ and $C(b_i, a_i)$ for all $1 \leq i \leq (n - 1)$. (i.e. $|C(a_i, b_i) \cap C(b_i, a_i)|$)
Input
The input contains at most 15 sets. For each set:
The first line contains an integer $n$ ($2 \leq n \leq 10^5$).
The second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \leq c_i \leq n$).
The $i$-th of the last $(n - 1)$ lines contains $2$ integers $a_i, b_i$ ($1 \leq a_i, b_i \leq n$).
Output
For each set, $(n - 1)$ integers $R_1, R_2, \dots, R_{n - 1}$.
Sample Input
4 1 2 2 1 1 2 2 3 3 4 5 1 1 2 1 2 1 3 2 3 3 5 4 5
Sample Output
1 2 1 1 1 2 1