2202 年，新冠病毒疫情再次席卷 Y 国。作为 Y 国的研究人员，小 W 希望能找到对抗病毒的方法。

小 W 有一个实验装置，它由 $n$ 个节点和 $n-1$ 条双向管道构成，第 $i$ 条管道连接 $u_i$ 和 $v_i$，任意两个节点都可以通过管道互相到达。小 W 有四种操作设备，分别进行 ${\tt abcd}$ 四种操作中的一种。每个管道上都有恰好一种操作设备。第 $i$ 个管道上的操作设备会对病毒进行 $c_i$ 操作。

小 W 总共要做 $q$ 次实验。第 $i$ 次实验会选择两个节点 $s_i$ 和 $t_i$，然后小 W 将病毒放入编号为 $s_i$ 节点，让它通过最短路径到达编号为 $t_i$ 的节点后取出。病毒会依次被最短路径上的实验设备操作。

小 W 发现，如果某个操作序列正着操作和倒着操作是一样的，经过这个操作后病毒可能会出现不可控的变异。比如经过 ${\tt a}$、${\tt abba}$ 或 ${\tt cabac}$ 操作的病毒是不可控的，而经过 ${\tt ab}$ 或 ${\tt bba}$ 操作的病毒则不是。特别的，没有经过任何操作的初始病毒是可控的。

在一次实验中，若病毒到达某个节点 $u$ 时病毒是不可控的，则称节点 $u$ 是危险的。一次实验的危险程度定义为路径上危险节点的数量。

为了预估实验的危险，小 W 希望你告诉他每次实验的危险程度。

输入格式

第一行两个数 $n$ 和 $q$。

接下来 $n-1$ 行，每行两个数字 $u_i,v_i$ 和一个字符 $c_i$。

接下来 $q$ 行，每行两个数字 $s_i$ 和 $t_i$。

输出格式

$q$ 行，每行一个整数表示第 $i$ 次实验的危险程度。

样例数据

样例 1 输入

7 5
1 2 a
2 3 a
3 4 a
2 5 b
1 6 b
6 7 a
2 7
4 7
3 6
6 3
4 1

样例 1 输出

2
3
2
1
3

样例 1 解释

五次实验的总操作序列分别是：${\tt aba},{\tt aaaba},{\tt aab},{\tt baa},{\tt aaa}$。

以第一次实验为例：

到 $1$ 号点后操作序列为 ${\tt a}$，到 $7$ 号点后操作序列为 ${\tt aba}$，这两个操作序列正着操作与反着操作相同，所以 $1$ 和 $7$ 号点是危险的。

到 $2$ 号点后操作序列为 ${\tt ab}$，这个序列倒着操作是 ${\tt ba}$，与正着操作不同，所以不是危险的。

总共有 $2$ 个节点是危险的，所以这次实验的危险程度为 $2$。

样例 2 输入

12 12
1 2 a
2 3 b
3 4 a
4 5 b
5 6 b
6 7 a
7 8 b
8 9 a
9 10 b
10 11 a
11 12 b
1 12
2 12
3 12
4 12
5 12
6 12
7 12
8 12
9 12
10 12
11 12
12 12

样例 2 输出

3
3
2
2
4
3
3
2
2
1
1
0

子任务

Subtask 1 (5pts)： $n,q \le 100$。

Subtask 2 (12pts)： $n,q \le 2000$。

Subtask 3 (21pts)： $n,q \le 40000$。

Subtask 4 (17pts)： 保证树是一条链。

Subtask 5 (45pts)： 无特殊性质。

对于 $100\%$ 的数据，保证 $1\leq n,q\leq 10^5$，$1\leq u_i,v_i,s_i,t_i\leq n,c_i\in\{{\tt a},{\tt b},{\tt c},{\tt d}\}$。