Канделябра

В заколдованном замке, скрытом в темном лесу, живет ужасное Чудовище. Растопить лед в его сердце и вернуть ему человеческий облик, сняв заклятие, может только прекрасная девушка, которая полюбит его таким, какой он есть.

Но снять заклятье не так просто. Девушка должна найти самую длинную мелодичную подпоследовательность, написанную в вершинах канделябра, и произнести её во время полной луны. Канделябра представляет из себя связный граф из $n$ вершин и $n - 1$ ребер. В каждой вершине канделябры написана маленькая латинская буква от 'a' до 't'.

Путь --- это последовательность вершин, в которую каждая вершина может входить не более одного раза и все соседние вершины соединены ребром. Подпоследовательность --- это путь, из которого удалили некоторые элементы, не меняя порядок оставшихся. Подстрока --- это подпоследовательность, из которого удалили некоторое, возможно нулевое, количество вершин с начала и с конца. Подпоследовательность называется мелодичной, если не существует ее подстроки длинной больше одного, которая равна себе в перевернутом виде.

В первой строке входного файла задано число $n$ --- количество вершин в канделябре ($2\le n\le 5\cdot 10^4$).

В следующих $n-1$ строках описаны ребра. Ребро задаётся числами $x_i$ и $y_i$ --- номерами вершин, которые она соединяет ($1\le x_i,y_i \le n$, $x_i \neq y_i$). Гарантируется, что между любыми двумя вершинами существует единственный путь.

Вершины нумеруются с единицы.

В следующей строке находится последовательность маленьких латинских букв от 'a' до 't' длины $n$ --- буквы, которые написаны на соответствующих вершинах.

Выведите одно число --- максимальную длину мелодичной подпоследовательности.