题目描述

Mirko 用 $N$ 个 LED 灯来装饰圣诞树，它们的颜色是已知的，并且通过 $(N-1)$ 条电线连接。

Mirko 在大功告成后，仔细地品味自己的作品。他被一种叫作「回文段」的特殊图案所吸引。「回文段」指一条从 $u$ 至 $v$ 的路径，它满足从 $u$ 到 $v$ 的路径所包含灯的颜色等于从 $v$ 到 $u$ 的路径所包含灯的颜色。

求出圣诞树中最长的「回文段」。

输入格式

第一行，输入一个整数 $N$，表示 LED 灯的数量。

第二行，输入一个由 $N$ 个英文小写字母组成的字符串，其中第 $i$ 个字母代表第 $i$ 个灯的颜色。

接下来的 $(N-1)$ 行，每行输入两个整数 $A,B$，表示 $A,B$ 之间用一条电线连接。

输出格式

输出圣诞树中最长的「回文段」。

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

提示

数据范围及约定

对于 $100\%$ 的数据，$1 \le N \le 5 \times 10^4, 1 \le A,B \le N, A \neq B$。

说明

本题分值按 COCI 原题设置，满分 $110$。

题目译自 COCI2019-2020 CONTEST #3 T4 Drvca 。