#4231. 回忆树

内存限制:256 MiB 时间限制:10 Sec

题目描述

回忆树是树。
具体来说,是n个点n-1条边的无向连通图,点标号为1~n,每条边上有一个字符(出于简化目的,我们认为只有小写字母)。
对一棵回忆树来说,回忆当然是少不了的。
一次回忆是这样的:你想起过往,触及心底…唔,不对,我们要说题目。
这题中我们认为回忆是这样的:给定2个点u,v(u可能等于v)和一个非空字符串s,问从u到v的简单路径上的所有边按照到u的距离从小到大的顺序排列后,边上的字符依次拼接形成的字符串中给定的串s出现了多少次。

输入格式

第一行2个整数,依次为树中点的个数n和回忆的次数m。
接下来n-1行,每行2个整数u、v和1个小写字母c,表示回忆树的点u、v之间有一条边,边上的字符为c
接下来2m行表示m次回忆,每次回忆2行:第1行2个整数u、v,第2行给出回忆的字符串s。

输出格式

对于每次回忆,输出串s出现的次数。

样例

样例输入


			
12 3
1 2 w
2 3 w
3 4 x
4 5 w
5 6 w
6 7 x
7 8 w
8 9 w
9 10 x
10 11 w
11 12 w
1 7
wwx
1 12
www
1 12
w

样例输出


			
2
0
8

数据范围与提示

对于100%的数据,n<=100000,m<=100000,询问串的总长<=300000