Cho một cây có \(n\) đỉnh và \(n\ - \ 1\) cạnh. Mỗi đỉnh i được gán một giá trị nguyên \(c_{i}\).

Yêu cầu: Với mỗi đỉnh \(i\), hãy tính số lượng giá trị khác nhau xuất hiện trong cây con gốc tại đỉnh đó (bao gồm cả chính đỉnh \(i\)).

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq \ n \leq \ 100000\)) — số lượng đỉnh của cây.

• Dòng thứ hai chứa n số nguyên \(c_{1},\ c_{2},\ ...,\ c_{n}\ (1 \leq \ c_{i} \leq \ n\)) — giá trị của từng đỉnh.

• \(n\ - \ 1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u\) và\(\ v\) \((1 \leq \ u,\ v \leq \ n),\) biểu thị có một cạnh nối giữa đỉnh \(u\) và đỉnh \(v\).

Kết quả:

In ra \(n\) số nguyên, số thứ \(i\) là số lượng giá trị khác nhau trong cây con gốc tại đỉnh \(i.\) Các số cách nhau bởi dấu cách.

Ví dụ:

Input	Output
5 2 3 2 2 1 1 2 1 3 3 4 3 5	3 1 2 1 1