Description

Mirko decorates a Christmas tree with $N$ LED lights. Their colors are known, and they are connected by $(N-1)$ wires.

After finishing, Mirko carefully admires his work. He is attracted by a special pattern called a "palindrome segment". A "palindrome segment" is a path from $u$ to $v$ such that the sequence of light colors along the path from $u$ to $v$ is the same as the sequence of light colors along the path from $v$ to $u$.

Find the longest "palindrome segment" in the Christmas tree.

Input Format

The first line contains an integer $N$, the number of LED lights.

The second line contains a string of $N$ lowercase English letters, where the $i$-th letter represents the color of the $i$-th light.

The next $(N-1)$ lines each contain two integers $A, B$, indicating that $A$ and $B$ are connected by a wire.

Output Format

Output the longest "palindrome segment" in the Christmas tree.

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

3

4
aabb
1 2
1 3
3 4

2

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

5

Hint

Constraints

For $100\%$ of the testdata, $1 \le N \le 5 \times 10^4, 1 \le A, B \le N, A \neq B$.

Notes

The score of this problem is set according to the original COCI problem, with a full score of $110$.

Translated from COCI2019-2020 CONTEST #3 T4 Drvca.

Translated by ChatGPT 5