题目描述

Kris 选了一棵圣诞树，并决定用彩灯装饰它。

彩灯共有 $N$ 个，编号为 $1$ 到 $N$，由 $N-1$ 根导线连接，并保证所有彩灯连通，也就是说这些彩灯构成一棵树。每个彩灯都有一种颜色，用一个小写英文字母表示。

Kris 观察这些彩灯时，发现了所谓的回文段：对于两个固定的彩灯 $u$ 和 $v$，考虑树上从 $u$ 到 $v$ 的简单路径。如果沿 $u\to v$ 得到的颜色序列，和沿 $v\to u$ 得到的颜色序列完全相同，则这条路径上的彩灯序列称为一个回文段。

请求出最长回文段包含的彩灯数量。

输入格式

第一行包含一个整数 $N$，表示彩灯数量。

第二行包含一个长度为 $N$ 的小写英文字母串，第 $i$ 个字符表示第 $i$ 个彩灯的颜色。每个字母代表一种颜色。

接下来 $N-1$ 行，每行两个整数 $A,B$，表示彩灯 $A$ 和彩灯 $B$ 之间有一根导线直接相连。

输出格式

输出一行一个整数，表示最长回文段的长度。

数据范围

• $1 \le N \le 50000$
• $1 \le A,B \le N$，$A\ne B$

子任务

样例 1

输入

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

输出

3

说明

所有彩灯连成一条链，最长回文段为 a-n-a，长度为 $3$。

样例 2

输入

4
aabb
1 2
1 3
3 4

输出

2

样例 3

输入

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

输出

5