H. Virus Experiment
time limit per test
2.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

In 2202, the Coronavirus pandemic sweeps the country Y again. As a researcher in country Y, Dr. W hopes to find a way to fight the virus.

Dr. W has an experiment equipment, which consists of $$$n$$$ nodes and $$$n-1$$$ bidirectional pipes, the $$$i$$$-th pipe connects $$$u_i$$$, $$$v_i$$$. Any pair of nodes can reach each other through the pipe. Dr. W has four kinds of operating devices, which can perform one of the four operations of $$${\tt abcd}$$$ respectively. On each pipe, there is exactly one kind of operation that can be performed by the operating device. The operating device on the $$$i$$$-th pipe performs $$$c_i$$$ operation on the virus.

Dr. W will do experiments for $$$q$$$ times. In the $$$i$$$-th experiment, two nodes $$$s_i$$$, $$$t_i$$$ will be selected, and then Dr. W will put the virus into the node numbered $$$s_i$$$, let it reach the node numbered $$$t_i$$$ through the shortest path, and then take it out. Virus will be operated by the operating devices on the shortest path one by one.

Dr. W found that if a certain operation sequence is the same as the reverse of it, the virus may mutate uncontrollably after this operation. For example, a virus operated by $$${\tt a}$$$, $$${\tt abba}$$$ or $$${\tt cabac}$$$ is uncontrollable, while a virus operated by $$${\tt ab}$$$ or $$${\tt bba}$$$ are not. In particular, the initial virus without any operation is controllable.

In an experiment, if the virus is uncontrollable when it reaches a certain node $$$u$$$, the node $$$u$$$ is said to be dangerous. The risk level of an experiment is defined as the number of dangerous nodes on the path.

In order to estimate the risk of the experiments, Dr. W wants you to tell him the risk level of each experiment.

Input

The first line contains two integers $$$n$$$ and $$$q$$$.

Next $$$n-1$$$ lines, each with two integers $$$u_i,v_i$$$ and a character $$$c_i$$$.

Next $$$q$$$ lines, each with two integers $$$s_i$$$ and $$$t_i$$$.

Output

$$$q$$$ lines, each with an integer representing the risk level of an experiment.

Examples
Input
7 5
1 2 a
2 3 a
3 4 a
2 5 b
1 6 b
6 7 a
2 7
4 7
3 6
6 3
4 1
Output
2
3
2
1
3
Input
12 12
1 2 a
2 3 b
3 4 a
4 5 b
5 6 b
6 7 a
7 8 b
8 9 a
9 10 b
10 11 a
11 12 b
1 12
2 12
3 12
4 12
5 12
6 12
7 12
8 12
9 12
10 12
11 12
12 12
Output
3
3
2
2
4
3
3
2
2
1
1
0
Note

Subtask 1 (5pts): $$$n,q \le 100$$$.

Subtask 2 (12pts): $$$n,q \le 2000$$$.

Subtask 3 (21pts): $$$n,q \le 40000$$$.

Subtask 4 (17pts): The tree is guaranteed to be a chain.

Subtask 5 (45pts): No special properties.

For $$$100\%$$$ data, $$$1\leq n,q\leq 10^5$$$, $$$1\leq u_i,v_i,s_i,t_i\leq n,c_i\in\{{\tt a},{\tt b},{\tt c},{\tt d}\}$$$.

Explanation of example $$$1$$$

The total operation sequences of the five experiments are: $$${\tt aba}, {\tt aaaba}, {\tt aab}, {\tt baa}, {\tt aaa}$$$.

Take the first experiment as an example:

After reaching the node $$$1$$$, the operation sequence is $$${\tt a}$$$, and after reaching the node $$$7$$$, the operation sequence is $$${\tt aba}$$$. These two operation sequences are the same as the reverse, so node $$$1$$$ and node $$$7$$$ are dangerous.

After reaching the node $$$2$$$, the operation sequence is $$${\tt ab}$$$, and the reverse is $$${\tt ba}$$$, which is different from the original sequence, so it is not dangerous.

There are a total of $$$2$$$ nodes that are dangerous, so the risk level for this experiment is $$$2$$$.