Hossam 有一个未加权的树 $$$G$$$,顶点带有字母。
Hossam 将 $$$s(v, \, u)$$$ 定义为一个字符串,该字符串是通过记下 $$$G$$$ 树中从顶点 $$$v$$$ 到顶点 $$$u$$$ 的唯一简单路径上的所有字母而获得的。
字符串 $$$a$$$ 是字符串 $$$s$$$ 的子序列,如果 $$$a$$$ 可以通过删除几个(可能是零)字母从 $$$s$$$ 获得。例如,“dores”、“cf”和“for”是“codeforces”的子序列,而“decor”和“fork”则不是。
回文是从左到右和从右到左读相同的字符串。例如,“abacaba”是回文,但“abac”不是。
Hossam 将字符串 $$$s$$$ 的子回文定义为 $$$s$$$ 的子序列,即回文。例如,“k”、“abba”和“abhba”是字符串“abhbka”的子回文,但“abka”和“cat”不是。
Hossam 将字符串 $$$s$$$ 的最大子回文定义为 $$$s$$$ 的子回文,其长度是 $$$s$$$ 的所有子回文中的最大长度。例如,“abhbka”只有一个最大子回文——“abhba”。但也可能该字符串有几个最大子回文数:字符串“abcd”有$$$4$$$最大子回文数。
帮助 Hossam 找到 $$$G$$$ 树中所有 $$$s(v, \, u)$$$ 中最长的最大子回文的长度。
请注意,子回文是一个子序列,而不是子串。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 200$$$) — 测试用例的数量。
每个测试用例的第一行都有一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^3$$$) — 图中的顶点数。
第二行包含一个长度为$$$n$$$的字符串$$$s$$$,其中第$$$i$$$个符号表示顶点$$$i$$$上的字母。保证该字符串中的所有字符都是小写英文字母。
接下来的 $$$n - 1$$$ 行描述了树的边缘。每条边由两个整数 $$$v$$$ 和 $$$u$$$ 给出($$$1 \le v, \, u \le n$$$, $$$v \neq u$$$)。这两个数字意味着树中存在一条边 $$$(v, \, u)$$$。保证给定的边形成一棵树。
保证所有 $$$n$$$ 的总和不超过 $$$2 \cdot 10^3$$$。
输出
对于每个测试用例,输出一个整数 - 所有 $$$s(v, \, u)$$$ 中最长的最大子回文的长度。
示例
输入 #1
2 5 abaca 1 2 1 3 3 4 4 5 9 caabadedb 1 2 2 3 2 4 1 5 5 6 5 7 5 8 8 9
输出 #1
3 5
注意
在第一个示例中,最大子回文是在顶点 $$$1、\、3、\、5$$$ 中包含字母的“aaa”,或在顶点 $$$1、\、4、\、5$$$ 中包含字母的“aca”。
第一个示例中的树。
在第二个示例中,只有一个最大回文“bacab”,其顶点为 $$$4, \, 2, \, 1, \, 5, \, 9$$$ 中的字母。
第二个示例中的树。