D. Помеченное буквами дерево Arpa и забавные пути Mehrdad
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Если вдруг кто-то пропустил, у нас в стране Arpa чудесные девушки.

У Arpa есть подвешенное дерево (связный ациклический граф), состоящее из n вершин. Вершины пронумерованы от 1 до n, вершина 1 является корнем. На каждом ребре дерева написана некоторая буква. Mehrdad — фанат самовлюбленных вещей. Он называет строку самовлюбленной, если возможно переставить местами символы строки так, чтобы она стала палиндромом.

Он спросил Arpa про каждую вершину v, какая наибольшая длина среди простых путей в поддереве вершины v таких, что буквы на пути образуют самовлюбленную строку.

Входные данные

Первая строка содержит целое число n (1  ≤  n  ≤  5·105) — количество вершин в дереве.

Далее следует (n  -  1) строка, i-я из них содержит целое число pi + 1 и букву ci + 1 (1  ≤  pi + 1  ≤  i, ci + 1 — строчная буква латинского алфавита, между a и v включительно), которые означают, что между вершинами pi + 1 и i + 1 есть ребро и на нем написана буква ci + 1.

Выходные данные

Выведите n чисел. i-е из них должно быть равно наибольшей длине среди простых путей в поддереве вершины i таких, что буквы на пути образуют самовлюбленную строку.

Примеры
Входные данные
4
1 s
2 a
3 s
Выходные данные
3 1 1 0 
Входные данные
5
1 a
2 h
1 a
4 h
Выходные данные
4 1 0 1 0