1번 정점을 루트로 하는 \(N\)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점 \(i\)에는 고유한 색깔을 나타내는 정수 \(C_i\)가 칠해져 있다.

트리의 각 정점 \(i\)에 대하여, 정점 \(i\)를 루트로 하는 서브트리(Subtree)에 포함된 정점들이 가진 '서로 다른 색깔의 종류의 수'를 구하는 프로그램을 작성하시오.

정점 \(i\)의 서브트리에는 정점 \(i\) 자신도 포함된다.

입력

첫째 줄에 트리의 정점의 수 \(N\)이 주어진다.

둘째 줄에는 1번 정점부터 \(N\)번 정점까지의 색깔을 나타내는 \(N\)개의 정수 \(C_1, C_2, ..., C_N\)이 공백을 사이에 두고 주어진다.

셋째 줄부터 \(N-1\)개의 줄에 걸쳐 트리의 간선 정보인 두 정수 \(u, v\)가 공백을 사이에 두고 주어진다.

이는 정점 \(u\)와 정점 \(v\)가 간선으로 연결되어 있음을 의미한다.

(입력으로 주어지는 그래프는 항상 올바른 트리 구조임이 보장된다.)

출력

첫째 줄부터 \(N\)개의 줄에 걸쳐 정답을 출력해야 한다.

\(i\)번째 줄에는 정점 \(i\)를 루트로 하는 서브트리 내에 존재하는 서로 다른 색깔의 종류의 수를 출력한다.

제한사항

• \(1 \le N \le 100,000\)
• \(1 \le C_i \le 100,000\)
• \(1 \le u, v \le N\) (\(u \ne v\))

예제 입력 1

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

예제 출력 1

3
2
1
1
1

예제 입력 2

3
5 5 5
1 2
2 3

예제 출력 2

1
1
1