1142 : Tree Intersection

Description

Bobo has a tree with n vertices numbered by 1,2,…,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 ≤ i ≤ (n − 1). (i.e. |C(a_i, b_i) ∩ C(b_i, a_i)|)

Input

The input contains at most 15 sets. For each set:

The first line contains an integer n(2 ≤ n ≤ 10⁵).

The second line contains n integers c₁, c₂, …, c_n(1 ≤ c_i ≤ n).

The i-th of the last (n-1) lines contains 2 integers a_i, b_i(1 ≤ a_i, b_i ≤ n).

Output

For each set, (n-1) integers R₁, R₂, …, R_n − 1.

Sample

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

1
2
1
1
1
2
1

Hint

Source

Author

ftiasch