题目描述

给定一颗 $n$ 个节点的无根树，每条边上附有一个小写英文字母。

于是一条路径对应一个字符串。

一共有 $q$ 次询问，每次询问以节点 $u$ 为起点的非空字符串中有多少字典序严格小于字符串 $u \leadsto v$。

输入格式

第一行，两个整数 $n, q$。

接下来 $n - 1$ 行，每行两个整数，一个小写字母：$u, v, c$。表示存在字母为 $c$ 的树边 $(u, v)$。保证 $u \neq v$。

接下来 $q$ 行，每行两个整数 $u, v$。

输出格式

$q$ 行，每行一个答案。

样例 1

输入

4 3
4 1 t
3 2 p
1 2 s
3 2
1 3
2 1

输出

0
1
1

解释：

• 第一个询问，以 $3$ 为起点的字符串有 p, ps, pst。$3 \leadsto 2$ 生成 p。没有比 p 字典序严格小的字符串。
• 第二个询问，以 $1$ 为起点的字符串有 s, sp, t。$1 \leadsto 3$ 生成 sp。s 字典序比 sp 小。
• 第三个询问，以 $2$ 为起点的字符串有 p, s, st。$2 \leadsto 1$ 生成 s。p 字典序比 s 小。

样例 2

输入

8 4
4 6 p
3 7 o
7 8 p
4 5 d
1 3 o
4 3 p
3 2 e
8 6
3 7
8 1
4 3

输出

6
1
3
1

数据范围与提示

$n \le 4000, q \le 500000$