Дерево

Задано підвішене дерево, яке містить $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$.

Приклади