Mirko 为即将到来的节日选择了一棵圣诞树，并决定用圣诞彩灯来装饰它。圣诞彩灯包含 $N$ 个 LED 灯，它们通过 $N - 1$ 条导线连接，使得所有彩灯都连通。此外，我们已知每个彩灯的颜色。
在装饰完树后，Mirko 自豪地凝视着他的杰作。过了一会儿，他开始注意到不同的图案。在这些图案中，他特别对所谓的“回文片段”感到惊奇。回文片段是指介于两个固定彩灯 $u$ 和 $v$ 之间的彩灯路径，使得从 $u$ 到 $v$ 路径上的颜色序列与从 $v$ 到 $u$ 路径上的颜色序列完全相同。请确定最长回文片段的长度（以该片段上的彩灯数量表示）。
输入格式
第一行包含一个整数 $N$ ($1 \le N \le 50\,000$)，表示彩灯的数量。
第二行包含一个由 $N$ 个英文小写字母组成的字符串，其中第 $i$ 个字母表示第 $i$ 个彩灯的颜色。
接下来的 $N - 1$ 行，每行包含两个整数 $A$ 和 $B$ ($1 \le A, B \le N, A \ne B$)，表示彩灯 $A$ 和 $B$ 之间直接由一根导线相连。
输出格式
输出第一行应包含最长回文片段的长度。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 17 | $N \le 3000$ |
| 2 | 25 | 彩灯 $i$ 与彩灯 $i+1$ 直接相连 ($1 \le i < N$)。 |
| 3 | 31 | 最多有 100 个彩灯与恰好一个其他彩灯直接相连。 |
| 4 | 37 | 无附加限制。 |
样例
输入样例 1
7 imanade 1 2 2 3 3 4 4 5 5 6 6 7
输出样例 1
3
输入样例 2
4 aabb 1 2 1 3 3 4
输出样例 2
2
输入样例 3
8 acdbabcd 1 6 6 7 6 3 3 4 4 5 5 2 8 5
输出样例 3
5