Задано подвешенное дерево, содержащее $n\:(1 \le n \le 10^6)$ вершин. Каждая вершина покрашена в один из $n$ цветов. Требуется для каждой вершины $v$ вычислить количество различных цветов, встречающихся в поддереве с корнем $v$. \InputFile В первой строке задано число $n$. Следующие $n$ строк описывают вершины по одной в строке. Описание очередной вершины $i$ имеет вид $p_i\:c_i$, где $p_i$ --- номер родителя вершины $i$, а $c_i$ --- цвет вершины $i\:(1 \le c_i \le n)$. Для корня дерева $p_i = 0$. \OutputFile Выведите $n$ чисел, обозначающих количества различных цветов в поддеревьях с корнями в вершинах $1, 2, ..., n$. \includegraphics{https://eolympusercontent.com/images/r241c0gc3910nee7ipo0t5pp48.gif}