У Хоссама есть невзвешенное дерево \(G\), в вершинах которого записаны буквы.
Через \(s(v, \, u)\) Хоссам обозначает строку, которая получается при написании всех букв на единственном простом пути из вершины \(v\) в вершину \(u\) в дереве \(G\).
Строка \(a\) является подпоследовательностью строки \(s\), если \(a\) может быть получена из \(s\) путем удаления нескольких символов (возможно, ни одного). Например, «dores», «cf» и «for» являются подпоследовательностями «codeforces», а «decor» и «fork» не являются.
Палиндромом называется строка, читающаяся одинаково слева направо и справа налево. Например, «abacaba» — палиндром, а «abac» — нет.
Под-палиндромом строки \(s\) Хоссам называет подпоследовательность \(s\), являющуюся палиндромом. Например, «k», «abba» и «abhba» являются под-палиндромом строки «abhbka», а «abka» и «cat» — нет.
Максимальным под-палиндромом строки \(s\) Хоссам называет под-палиндром \(s\), имеющий максимальную длину среди всех под-палиндромов \(s\). Например, у строки «abhbka» есть только один максимальный под-палиндром — «abhba». Но может быть и так, что у строки несколько максимальных под-палиндромов: у строки «abcd» целых \(4\) максимальных под-палиндрома.
Хоссам просит вас найти длину самого длинного максимального под-палиндрома среди всех \(s(v, \, u)\) в заданном дереве \(G\).
Еще раз обращаем Ваше внимание на то, что под-палиндром — это подпоследовательность, а не подстрока.
Выходные данные
Для каждого набора входных данных выведите одно число — длину самого длинного максимального под-палиндрома среди всех \(s(v, \, u)\).
Примечание
В первом примере искомым подпалиндромом может быть «aaa», символы которого расположены в вершинах \(1, \, 3, \, 5\) или «aca», символы которого расположены в вершинах \(1, \, 4, \, 5\).
Дерево из первого примера. Во втором примере единственным искомым палиндромом является «bacab», символы которого расположены в вершинах \(4, \, 2, \, 1, \, 5, \, 9\).
Дерево из второго примера.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5
abaca
1 2
1 3
3 4
4 5
9
caabadedb
1 2
2 3
2 4
1 5
5 6
5 7
5 8
8 9
|
3
5
|