eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Дерево

Дерево

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

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

Приклад

Вхідні дані #1
5
2 1
3 2
0 3
3 3
2 1
Вихідні дані #1
1 2 3 1 1
Джерело 2012 Зимняя школа Харьков, День Гольдштейна