촛대

어두운 숲 깊숙한 곳의 저주받은 성에 무시무시한 괴물이 살고 있다. 괴물의 가슴에 맺힌 얼음을 녹이고 사람의 모습을 되찾게 할 수 있는 이는, 있는 그대로의 그를 사랑해 줄 아름다운 처녀뿐이다.

저주를 푸는 일은 쉽지 않다. 처녀는 촛대의 정점마다 적힌 글자로 이루어진 가장 긴 멜로디 부분열을 찾아, 보름달이 뜬 밤에 소리 내어 읽어야 한다.

촛대는 $n$개의 정점과 $n-1$개의 간선으로 이루어진 연결 그래프다. 각 정점에는 'a'부터 't'까지의 소문자 하나가 적혀 있다.

경로는 각 정점을 최대 한 번만 지나며, 인접한 정점끼리 간선으로 이어진 정점들의 나열이다. 부분열은 경로에서 일부 원소를 지우고 남은 원소의 순서를 그대로 둔 것이다. 부분 문자열은 부분열의 앞과 뒤에서 0개 이상의 정점을 지운 것이다. 어떤 부분 문자열도 길이가 1보다 크고 뒤집어도 같은 것이 되지 않으면, 그 부분열을 멜로디하다고 한다.

첫 줄에 정점의 개수 $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$). 임의의 두 정점 사이의 경로는 하나뿐이다. 마지막 줄에는 길이 $n$의 소문자 문자열이 주어지며, $i$번째 글자는 $i$번 정점에 적혀 있다.

멜로디한 부분열의 최대 길이를 한 줄에 출력한다.