Candelabra

A terrible Monster lives in a cursed castle hidden deep in a dark forest. Only a beautiful girl who loves him as he is can melt the ice in his heart and restore his human form.

Breaking the curse is not easy. The girl must find the longest melodic subsequence written on the vertices of a candelabra and recite it under the full moon.

The candelabra is a connected graph with $n$ vertices and $n-1$ edges. Each vertex has a lowercase Latin letter from 'a' to 't' written on it.

A path is a sequence of vertices in which each vertex appears at most once and every two adjacent vertices are connected by an edge. A subsequence is a path with some elements removed, keeping the order of the remaining elements. A substring is a subsequence with zero or more vertices removed from the beginning and the end. A subsequence is called melodic if it has no substring of length greater than one that equals its reverse.

The first line contains $n$ ($2\le n\le 5\cdot 10^4$), the number of vertices. Each of the next $n-1$ lines contains two integers $x_i$ and $y_i$ ($1\le x_i,y_i \le n$, $x_i \neq y_i$), the vertices joined by an edge. There is exactly one path between any two vertices. The last line contains a string of $n$ lowercase letters from 'a' to 't', where the $i$-th letter is written on vertex $i$.

Print one integer, the maximum length of a melodic subsequence.