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.
The first line contains the number n. The next n lines describe the vertices. The description of the vertex i has the form pici, where pi is the parent number of the vertex i, and ci is the color of the vertex i(1≤ci≤n). For the root of the tree pi=0.
Print n numbers, denoting the number of different colors in the subtrees rooted at the vertices 1,2,...,n.