Дано дерево (связный ациклический граф) на n вершинах. Вершины пронумерованы от 1 до n и на каждой вершине записана буква английского алфавита от a до t.
Путь в дереве называется палиндромным, если из букв, записанных на нём, можно составить палиндром (буквы можно произвольным образом переставлять).
Для каждой вершины выведите количество палиндромных путей, проходящих через неё.
Учтите, что путь из вершины u в вершину v и путь из вершины v в вершину u считаются одинаковыми, такие пути должны учитываться ровно один раз.
Выходные данные
Выведите n чисел, где i-е число обозначает количество палиндромных путей, проходящих через вершину i.
Примечание
В первом тестовом примере следующие пути являются палиндромными:
2 - 3 - 4
2 - 3 - 5
4 - 3 - 5
Кроме того, все пути, состоящие из одной вершины, являются палиндромными. А следующие пути палиндромными не являются:
1 - 2 - 3
1 - 2 - 3 - 4
1 - 2 - 3 - 5
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2
2 3
3 4
3 5
abcbb
|
1 3 4 3 3
|
|
2
|
7
6 2
4 3
3 7
5 2
7 2
1 4
afefdfs
|
1 4 1 1 2 4 2
|