В заколдованном замке, скрытом в темном лесу, живет ужасное Чудовище. Растопить лед в его сердце и вернуть ему человеческий облик, сняв заклятие, может только прекрасная девушка, которая полюбит его таким, какой он есть.
Но снять заклятье не так просто. Девушка должна найти самую длинную мелодичную подпоследовательность, написанную в вершинах канделябра, и произнести её во время полной луны. Канделябра представляет из себя связный граф из n вершин и n - 1 ребер. В каждой вершине канделябры написана маленькая латинская буква от 'a' до 't'.
Путь — это последовательность вершин, в которую каждая вершина может входить не более одного раза и все соседние вершины соединены ребром. Подпоследовательность — это путь, из которого удалили некоторые элементы, не меняя порядок оставшихся. Подстрока — это подпоследовательность, из которого удалили некоторое, возможно нулевое, количество вершин с начала и с конца. Подпоследовательность называется мелодичной, если не существует ее подстроки длинной больше одного, которая равна себе в перевернутом виде.
В первой строке входного файла задано число n — количество вершин в канделябре (2 ≤ n ≤ 5·104).
В следующих n - 1 строках описаны ребра. Ребро задаётся числами xi и yi — номерами вершин, которые она соединяет (1 ≤ xi, yi ≤ n, xi ≠ yi). Гарантируется, что между любыми двумя вершинами существует единственный путь.
Вершины нумеруются с единицы.
В следующей строке находится последовательность маленьких латинских букв от 'a' до 't' длины n — буквы, которые написаны на соответствующих вершинах.
Выведите одно число — максимальную длину мелодичной подпоследовательности.
Первая группа тестов состоит из тестов, для которых выполняются ограничения n ≤ 100. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 22 баллов.
Вторая группа тестов состоит из тестов, для которых выполняются ограничения n ≤ 1000. Баллы за эту группу начисляются только при прохождении всех тестов группы и всех предыдущих групп. Стоимость группы составляет 21 баллов.
Третья группа тестов состоит из тестов, для которых выполняются ограничения: в последовательность входят только буквы 'a' и 'b'. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 8 баллов.
Четвертая группа тестов состоит из тестов, для которых выполняются ограничения: в последовательность входят только буквы c 'a' по 'j'. Баллы за эту группу начисляются только при прохождении всех тестов группы и всех предыдущих групп. Стоимость группы составляет 29 баллов.
Пятая группа тестов состоит из тестов, для которых выполняются полные ограничения. Баллы за эту группу начисляются только при прохождении всех тестов группы и всех предыдущих групп. Стоимость группы составляет 20 баллов.
Обратите внимание на возможность узнать результат проверки вашего решения на всех тестах, нажав на ссылку «Запросить информацию о проверке» на вкладке «Решения».
5
1 2
4 1
4 5
2 3
acbcb
4