Cho một cây có gốc gồm \(n\) nút. Các nút được đánh số từ \(1, 2, ..., n\), và nút \(1\) là gốc của cây. Mỗi nút có một màu.

Nhiệm vụ của bạn là xác định với mỗi nút số lượng các màu khác nhau trong cây con của nút đó.

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên \(n\): số lượng nút. Các nút được đánh số từ \(1\) đến \(n\).
• Dòng tiếp theo gồm \(n\) số nguyên \(c_1, c_2, ..., c_n\): màu của mỗi nút.
• Sau đó có \(n - 1\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): có một cạnh nối giữa các nút \(a\) và \(b\).

Dữ liệu ra:

• In ra \(n\) số nguyên: đối với mỗi nút từ \(1\) đến \(n\), số lượng màu khác nhau trong cây con của nút đó.

Ràng buộc

• \(1 \le n \le 2 \times 10^5\)
• \(1 \le a,b \le n\)
• \(1 \le c_i \le 10^9\)

Input 1

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

Output1

3 1 2 1 1