The hanging tree contains vertices. Each vertex is colored in one of colors. For each vertex find the number of different colors, occurring in the subtree with root .
The first line contains the number . The next lines describe the vertices. The description of the vertex has the form , where is the parent number of the vertex , and is the color of the vertex . For the root of the tree .
Print numbers, denoting the number of different colors in the subtrees rooted at the vertices .