Competitions

# 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

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