Jeroen 发现了一棵由 $n$ 个节点组成的优美树。请帮他在树上涂鸦。Jeroen 通过在每个节点上喷涂一个字母来对树进行涂鸦。他有一个最喜欢的单词，他想要最大化树中满足以下条件的有向路径 $u \to v$ 的数量：路径上的字母序列 $u, p_2, p_3, \dots, v$ 拼写出他最喜欢的单词。

注意，有向路径是指由 1 个或多个节点组成的序列，其中序列中相邻的节点在树中是相邻的，且序列中没有节点出现超过一次。树本身是无向的，因此每条边都可以双向遍历。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 300\,000$)，表示树的节点数。

下一行包含一个字符串 $w$ ($1 \le |w| \le 3$)，仅由小写字母组成，表示 Jeroen 最喜欢的单词。

接下来的 $n - 1$ 行中的每一行包含一条边的描述。每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示一条连接节点 $u_i$ 和节点 $v_i$ 的边。

保证 $n - 1$ 条边构成一棵树。

输出格式

输出一个整数，表示如果最优地喷涂字母，拼写出 Jeroen 最喜欢的单词的有向路径的最大数量。

样例

样例输入 1

1
a

样例输出 1

1

样例输入 2

3
orz
1 2
2 3

样例输出 2

1

样例输入 3

2
ab
1 2

样例输出 3

1

样例输入 4

5
bob
3 2
5 1
1 4
2 4

样例输出 4

4

说明

对于最后一个样例，一种最优的字母喷涂方式如下：

样例 4 的可视化

此处包含单词 bob 的有向路径为：

• $4 \to 1 \to 5$
• $5 \to 1 \to 4$
• $4 \to 2 \to 3$
• $3 \to 2 \to 4$

总计得到 4 条拼写出单词 bob 的有向路径，这是最优解。