Mirko chose a Christmas tree for the upcoming holidays and decided to decorate it with Christmas lights. Christmas lights contain $N$ LED lights that are connected via $N-1$ conductive wires such that all of the lights are connected. Additionally, we know the color of each Christmas light.

After he decorated the tree, Mirko proudly stared at his masterpiece. After a while, he started noticing different patterns. Among those patterns, he was particularly amazed by so-called palindromic segments. Palindromic segment is a segment of Christmas lights on the path between two fixed lights, $u$ and $v$, such that the array of colors on a path from $u$ to $v$ is exactly the same as the array of colors on the path from $v$ to $u$. Determine the length of the longest palindromic segment expressed in the number of lights on that segment.

Input

The first line contains an integer $N$ $(1\le N\le 50000)$ from the task description.

The next line contains an array of $N$ lowercase letters from the English alphabet where the $i$-th letter represents the color of the $i$-th Christmas light.

Each of the next $N-1$ lines contains two integers $A$ and $B$ $(1\le A,B\le N,A\ne B)$, which denote that lights $A$ and $B$ are directly connected by a conducting wire.

Output

The first line of output should contain the length of the longest palindromic segment.

Scoring

Subtask	Score	Constraints
$1$	$17$	$N\le 3000$
$2$	$25$	Light $i$ is directly connected with light $i+1$ $(1\le i<N)$.
$3$	$31$	At most $100$ lights are directly connected with exactly one other light.
$4$	$37$	No additional constraints.

Sample Input 1

7
imanade
1 2
2 3
3 4
4 5
5 6
6 7

Sample Output 1

3

Sample Input 2

4
aabb
1 2
1 3
3 4

Sample Output 2

2

Sample Input 3

8
acdbabcd
1 6
6 7
6 3
3 4
4 5
5 2
8 5

Sample Output 3

5