题目描述

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

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

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

输入格式

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

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

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

输出格式

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

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

0
1
1

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$