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