题目描述

给定一棵 $n$ 个点的树，每条边上有一个字符。定义 $S(x, y)$ 为 $x$ 到 $y$ 的简单路径上所有字符按顺序组成的字符串。

给定一个长为 $m$ 的串 $T$，求对于树上任意两个点 $1 \le x,y \le n$，$\operatorname{LCS}(S(x, y), T)$ 的最长长度。

其中，$\operatorname{LCS}(P, Q)$ 表示两个字符串的最长公共子序列长度。例如 $\operatorname{LCS}(\texttt{abcde},\texttt{bdc}) = \operatorname{length}(\texttt{bd})=2$。

输入格式

第一行一个整数 $T$，表示数据组数。

接下来 $T$ 组数据，对于每组数据：

第一行两个整数 $n,m$。

接下来 $n-1$ 行，每行两个整数 $u,v$ 以及一个小写字母 $c$，表示一条连接结点 $u,v$ 的边，边上的字符为 $c$。

最后一行一个长度为 $m$ 的字符串 $T$。

输出格式

共 $T$ 行，每行一个整数表示答案。

3
5 4
1 2 a
2 3 c
2 4 d
1 5 b
cfgd
6 4
1 2 a
2 3 c
2 4 d
1 5 b
3 6 d
abcd
3 1
1 3 a
2 3 a
b

2
3
0

数据范围

• 对于 $30\%$ 的数据，对于所有的 $2 \le i \le n - 1$，节点 $i$ 仅与节点 $i-1$ 和 $i+1$ 相连；
• 对于 $60\%$ 的数据，对于所有的 $2 \le i \le n$，节点 $i$ 仅与至多两个节点相连；
• 对于 $100\%$ 的数据，$1 \le T \le 500$，$2 \le n, \sum n \le 10^4$，$1 \le m \le 10^3$，字符串 $S$ 中仅包含小写英文字母。