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 Зимняя школа Харьков, День Гольдштейна