The hanging tree contains n (1 ≤ n ≤ 106) 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 (1 ≤ ci ≤ n). 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.