U108159 [COCI2019-2020 #3]Lampice

Mirko 准备用 $N$ 个 LED 灯来装饰圣诞树。这 $N$ 个灯通过了 $N-1$ 根电线连接在一起，任意两个灯之间都能通过电线互相到达。并且我们知道所有灯的颜色。 装饰结束后，Mirko 发现了很多有趣的图案，其中他最感兴趣的是 **palindromic segments**。一个 palindromic segments 是一条灯 $u$ 和灯 $v$ 之间的路径，满足从 $u$ 到 $v$ 经过的灯的颜色序列和从从 $v$ 到 $u$ 经过的灯的颜色序列相同。 Mirko 想要知道最长的 palindromic segments 有多长。一个 palindromic segments 长度定义为这条路径上灯的个数。

第一行包含一个整数 $N$，表示灯的个数。 第二行包含一个长度为 $N$ 的字符串，仅由小写字母组成，其中第 $i$ 个字符表示第 $i$ 个灯的颜色。 接下里 $N-1$ 行，每行包含两个整数 $A$ 和 $B$ ($A \neq B$)，表示灯 $A$ 和 灯 $B$ 之间有一条电线直接相连。

仅一行，包含一个整数表示最长的 palindromic segments 的长度。

**本题采用捆绑测试，各个子任务限制与得分如下。** 子任务 1（15 分）：$1 \le N \le 3 \times 10^3$； 子任务 2（25 分）：灯 $i$ 和灯 $i+1$ ($1 \le i