Cho một cây gồm ~n~ đỉnh có gốc tại đỉnh ~1~. Đỉnh thứ ~i~ (~1 \leq i \leq n~) được gán màu sắc là ~c_i~.

Với mỗi đỉnh ~i~, xác định số màu sắc phân biệt có trong cây con gốc ~i~.

Input

• Dòng đầu chứa số nguyên dương ~n~ (~1 \leq n \leq 2 \times 10^5~).

• Dòng thứ hai chứa ~n~ số nguyên dương cách nhau bởi dấu cách biểu diễn mảng ~c~, với ~c_i~ là màu sắc của đỉnh thứ ~i~ (~1 \leq c_i \leq 10^9~).

• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a, b~ biểu diễn một cạnh hai chiều giữa đỉnh ~a~ và ~b~ (~1 \leq a,b \leq n~).

Output

Gồm một dòng duy nhất chứa ~n~ số nguyên cách nhau bởi dấu cách, số thứ ~i~ là số màu sắc phân biệt trong tất cả các đỉnh thuộc cây con gốc ~i~.

Scoring

Sample Input 1

5
2 3 2 2 1
1 2
1 3
3 4
3 5

Sample Output 1

3 1 2 1 1

Sample Input 2

4
1 1 3 1000
1 2
2 3
2 4

Sample Output 2

3 3 1 1

Notes

• Trong test đầu tiên, cây con của đỉnh ~1~ bao gồm tất cả các đỉnh trong cây, mang ~3~ giá trị màu sắc khác nhau. Cây con của đỉnh ~3~ bao gồm ba đỉnh là ~3, 4, 5~ lần lượt mang các màu ~2, 2, 1~, có tất cả ~2~ màu sắc phân biệt là màu ~1~ và ~2~.

• Trong test thứ hai, cây con của đỉnh ~1~ và đỉnh ~2~ đều có ~3~ màu sắc phân biệt là màu ~1, 3, 1000~.