CF786D.Rap God

Rick is in love with Unity. But Mr. Meeseeks also love Unity, so Rick and Mr. Meeseeks are "love rivals".

Unity loves rap, so it decided that they have to compete in a rap game (battle) in order to choose the best. Rick is too nerds, so instead he's gonna make his verse with running his original algorithm on lyrics "Rap God" song.

His algorithm is a little bit complicated. He's made a tree with n vertices numbered from 1 to n and there's a lowercase english letter written on each edge. He denotes str(a, b) to be the string made by writing characters on edges on the shortest path from a to b one by one (a string of length equal to distance of a to b). Note that str(a, b) is reverse of str(b, a) and str(a, a) is empty.

In order to make the best verse he can, he needs to answer some queries, but he's not a computer scientist and is not able to answer those queries, so he asked you to help him. Each query is characterized by two vertices x and y (x ≠ y). Answer to this query is the number of vertices like z such that z ≠ x, z ≠ y and str(x, y) is lexicographically larger than str(x, z).

String x  =  _x_1_x_2...x|x| is lexicographically larger than string y  =  _y_1_y_2...y|y|, if either |x|  >  |y| and _x_1  =  _y_1,  _x_2  =  _y_2,  ...,  x|y|  =  y|y|, or exists such number r (r  <  |x|,  r  <  |y|), that _x_1  =  _y_1,  _x_2  =  _y_2,  ...,  x__r  =  y__r and x__r  +  1  >  y__r  +  1. Characters are compared like their ASCII codes (or alphabetic order).

Help Rick get the girl (or whatever gender Unity has).

瑞克爱上了Unity。但米西克斯先生也爱Unity，因此瑞克与米西克斯先生成了“情敌”。

Unity热爱说唱，于是决定让他们通过一场说唱对决（battle）来一决高下，从而选出最优秀者。瑞克太书呆子气了，所以他打算用自己原创的算法处理《Rap God》这首歌的歌词，来创作自己的说唱歌词。

他的算法略显复杂：他构建了一棵含 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$，每条边上写有一个小写英文字母。记 $\mathrm{str}(a,\,b)$ 为从顶点 $a$ 到顶点 $b$ 的最短路径上各边所写字符依次连接而成的字符串（其长度等于 $a$ 与 $b$ 之间的距离）。注意：$\mathrm{str}(a,\,b)$ 是 $\mathrm{str}(b,\,a)$ 的逆序，且 $\mathrm{str}(a,\,a)$ 为空字符串。

为了写出最佳说唱歌词，他需要回答若干查询；但他并非计算机科学家，无法自行解答这些查询，于是向你求助。每个查询由两个顶点 $x$ 和 $y$ 给出（满足 $x \ne y$）。该查询的答案是：满足以下条件的顶点 $z$ 的数量：

• $z \ne x$，
• $z \ne y$，
• 且 $\mathrm{str}(x,\,y)$ 在字典序上严格大于 $\mathrm{str}(x,\,z)$。

字符串 $x = x_1x_2\ldots x_{|x|}$ 在字典序上大于字符串 $y = y_1y_2\ldots y_{|y|}$，当且仅当以下任一条件成立：

• $|x| > |y|$，且 $x_1 = y_1,\, x_2 = y_2,\, \ldots,\, x_{|y|} = y_{|y|}$；
• 或存在某个整数 $r$（满足 $r < |x|$ 且 $r < |y|$），使得 $x_1 = y_1,\, x_2 = y_2,\, \ldots,\, x_r = y_r$，但 $x_{r+1} > y_{r+1}$。
  其中字符之间的大小关系按其 ASCII 码值（或字母表顺序）比较。

请帮助瑞克赢得佳人芳心（或无论 Unity 属于何种性别）。

The first line of input contain two integers n and q (2 ≤ n ≤ 20000, 1 ≤ q ≤ 20000) — number of vertices in tree and number of queries respectively.

The next n - 1 lines contain the edges. Each line contains two integers v and u (endpoints of the edge) followed by an English lowercase letter c (1 ≤ v, u ≤ n, v ≠ u).

The next q line contain the queries. Each line contains two integers x and y (1 ≤ x, y ≤ n, x ≠ y).

输入的第一行包含两个整数 $n$ 和 $q$（$2 \leq n \leq 20000$，$1 \leq q \leq 20000$），分别表示树中顶点的数量和查询的数量。

接下来的 $n-1$ 行描述树的边。每行包含两个整数 $v$ 和 $u$（边的两个端点），后跟一个英文小写字母 $c$（$1 \leq v, u \leq n$，$v \neq u$）。

接下来的 $q$ 行描述查询。每行包含两个整数 $x$ 和 $y$（$1 \leq x, y \leq n$，$x \neq y$）。

Print the answer for each query in one line.

每行输出一个查询的答案。

Here's the tree of first sample testcase:

Here's the tree of second sample testcase:

In this test:

• str(8, 1) = poo
• str(8, 2) = poe
• str(8, 3) = po
• str(8, 4) = pop
• str(8, 5) = popd
• str(8, 6) = popp
• str(8, 7) = p

So, for the first query, and for the third query is the answer.

第一个样例测试用例的树结构如下：

第二个样例测试用例的树结构如下：

在本测试中：

• str(8, 1) = poo
• str(8, 2) = poe
• str(8, 3) = po
• str(8, 4) = pop
• str(8, 5) = popd
• str(8, 6) = popp
• str(8, 7) = p

因此，对于第一个查询，答案为 ；对于第三个查询，答案为 。