Дерево

Задано подвешенное дерево, содержащее $n(1\le n\le 10^6)$ вершин. Каждая вершина покрашена в один из $n$ цветов. Требуется для каждой вершины $v$ вычислить количество различных цветов, встречающихся в поддереве с корнем $v$.

Входные данные

В первой строке задано число $n$. Следующие $n$ строк описывают вершины по одной в строке. Описание очередной вершины $i$ имеет вид $p_i{c}_i$, где $p_i$ — номер родителя вершины $i$, а $c_i$ — цвет вершины $i(1\le c_i\le n)$. Для корня дерева $p_i=0$.

Выходные данные

Выведите $n$ чисел, обозначающих количества различных цветов в поддеревьях с корнями в вершинах $1,2,...,n$.

Примеры