Задано підвішене дерево, яке містить n(1≤n≤106) вершин. Кожну вершину пофарбовано у один з n кольорів. Потрібно для кожної вершини v обчислити кількість різних кольорів, які зустрічаються у піддереві з коренем v.
У першому рядку задано число n. Наступні n рядків описують вершини по одній у рядку. Опис чергової вершини i має вигляд pici, де pi — номер батька вершини i, а ci — колір вершини i(1≤ci≤n). Для кореня дерева pi=0.
Виведіть n чисел, які позначають кількості різних кольорів у піддеревах з коренями у вершинах 1,2,...,n.