芭芭拉冲鸭~（续）
题号：NC213912
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

芭芭拉这次来到了一棵字母树，这同样是一棵无根树，每个节点上面有一个小写字母。
芭芭拉想知道，自己从x冲刺到y，从x走到y收集所有字母，选择其中一部分字母组成一个回文串，这个回文串的最大长度是多少？
同样的，芭芭拉冲刺的时候是不能掉头的。
一共有q次询问。每次的询问是独立的（即本次收集字母不影响之后的询问，每次询问时字母都是未被收集状态）。

输入描述:

第一行有一个正整数。 
接下来的行，每行输入两个正整数和，代表和之间有一条无向边相连。 
接下来一行有一个长度为的字符串，字符串仅由小写字母构成。第个字符表示节点上的字母。 
接下来一行是一个正整数，代表询问次数。 
接下来的行，每行两个正整数和。 
（保证输入一定是一棵树）


输出描述:

对应每次询问，输出一个正整数，代表回文串的最大长度。
示例1

输入

复制 
5
1 2
1 3
2 4
2 5
abcba
3
4 5
1 2
3 3

输出

复制 
3
1
1

说明

这棵树的构造如下：

对于第一个询问，芭芭拉冲刺的路径是4-2-5，收集的字母有两个b一个a，可以构建的最长回文串是"bab"，长度为3。
对于第二个询问，芭芭拉冲刺的路径是1-2，收集的字母有一个b一个a，可以构建的最长回文串是"a"（也可以是"b"），长度为1。
对于第三个询问，芭芭拉起点和终点都是3，所以站在原地不动，收集的字母有只有一个c，可以构建的最长回文串是"c"，长度为1。