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$. \InputFile 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$. \OutputFile Print $n$ numbers, denoting the number of different colors in the subtrees rooted at the vertices $1, 2, ..., n$. \includegraphics{https://eolympusercontent.com/images/r241c0gc3910nee7ipo0t5pp48.gif}