Lampice

Time limit5sMemory limit512 MB

Summary

Given a tree whose nodes are colored letters, find the longest path whose color sequence reads the same in both directions, and report its number of nodes.

Level: Medium7 of 10
Topics: Tree, Divide and conquer, String matching
Solved: No attempts yet

Problem

Mirko chose a Christmas tree for the upcoming holidays and decided to decorate it with Christmas lights. The lights consist of $N$ LED lights connected by $(N-1)$ conductive wires, so that all of the lights are connected. Each light has a color.

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. A palindromic segment is a segment of lights on the path between two fixed lights $u$ and $v$ such that the array of colors on the 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 as the number of lights on that segment.

Input

The first line contains an integer $N$ ( $1 \le N \le 50\,000$ ).

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

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

Output

The first line of output contains the length of the longest palindromic segment.

Examples3

Example 1
Input
```
7
imanade
1 2
2 3
3 4
4 5
5 6
6 7
```
Expected output
```
3
```
Example 2
Input
```
4
aabb
1 2
1 3
3 4
```
Expected output
```
2
```

Example 3

Input

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

Expected output