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