e-olymp
Competitions

IOI Preparation - Trees

Tree

The hanging tree contains n (1n106) vertices. Each vertex is colored in one of n colors. For each vertex v find the number of different colors, occurring in the subtree with root v.

Input

The first line contains number n. Next n lines describe the vertices. The description of the vertex i has a form pi ci, where pi is the parent number of vertex i, and ci is the color of vertex i (1cin). For the root of the tree pi = 0.

Output

Print n numbers, denoting the number of different colors in the subtrees rooted at the vertices 1, 2, ..., n.

Time limit 2 seconds
Memory limit 256 MiB
Input example #1
5
2 1
3 2
0 3
3 3
2 1
Output example #1
1 2 3 1 1
Input example #2
1
0 1
Output example #2
1
Input example #3
2
0 1
1 1
Output example #3
1 1
Input example #4
2
0 1
1 2
Output example #4
2 1
Source 2012 Winter School, Kharkov, Goldshtein