Если вдруг кто-то пропустил, у нас в стране Arpa чудесные девушки.
У Arpa есть подвешенное дерево (связный ациклический граф), состоящее из n вершин. Вершины пронумерованы от 1 до n, вершина 1 является корнем. На каждом ребре дерева написана некоторая буква. Mehrdad — фанат самовлюбленных вещей. Он называет строку самовлюбленной, если возможно переставить местами символы строки так, чтобы она стала палиндромом.
Он спросил Arpa про каждую вершину v, какая наибольшая длина среди простых путей в поддереве вершины v таких, что буквы на пути образуют самовлюбленную строку.
Выходные данные
Выведите n чисел. i-е из них должно быть равно наибольшей длине среди простых путей в поддереве вершины i таких, что буквы на пути образуют самовлюбленную строку.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 s
2 a
3 s
|
3 1 1 0
|
|
2
|
5
1 a
2 h
1 a
4 h
|
4 1 0 1 0
|