给定一棵有 n 个顶点的树(连通的非循环无向图)。顶点从 1 到 n 编号,每个顶点分配一个从 a 到 t 的字符。
如果路径中标签的至少一个排列是回文,则称树中的路径是回文的。
对于每个顶点,输出经过它的回文路径的数量。
注意:从顶点 u 到顶点 v 的路径被认为与从顶点 v 到顶点 u 的路径相同,并且该路径对于其经过的每个顶点仅计数一次。
输入
第一行包含一个整数 n (2 ≤ n ≤ 2·105) — 树中的顶点数。
接下来的 n - 1 行每行包含两个整数 u 和 v (1 ≤ u, v ≤ n, u ≠ v),表示连接顶点 u 和顶点 v 的边。保证给定的图是一棵树。
下一行包含一个由从 a 到 t 的 n 个小写字符组成的字符串,其中第 i (1 ≤ i ≤ n) 个字符是树中顶点 i 的标签。
输出
在一行中打印n个整数,其中第i个是树中经过顶点i的回文路径的数量。
示例
输入 #1
5 1 2 2 3 3 4 3 5 abcbb
输出 #1
1 3 4 3 3
输入 #2
7 6 2 4 3 3 7 5 2 7 2 1 4 afefdfs
输出 #2
1 4 1 1 2 4 2
注意
在第一个示例案例中,以下路径是回文路径:
2 - 3 - 4
2 - 3 - 5
4 - 3 - 5
此外,所有仅包含一个顶点的路径都是回文路径。下面列出了第一个示例中的一些非回文路径:
1 - 2 - 3
1 - 2 - 3 - 4
1 - 2 - 3 - 5