题目描述

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

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

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

输入格式

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

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

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

输出格式

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

样例 1

input

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

output

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

input

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

output

6
1
3
1

数据范围与提示

$n\le 4000, q \le 500000$