Tree

The hanging tree contains $n(1\le n\le 10^6)$ 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 the number $n$. The next $n$ lines describe the vertices. The description of the vertex $i$ has the form $p_i{c}_i$, where $p_i$ is the parent number of the vertex $i$, and $c_i$ is the color of the vertex $i(1\le c_i\le n)$. For the root of the tree $p_i=0$.

Output

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

Examples