Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

Kazari loves to solve math problems.

In her opinion, all problems can be divided into three categories according to their difficulties - Easy, Medium and Hard, represented as $1, 2$ and $3$, respectively.

Today she goes to the forest and finds a strange tree with $n$ vertices: there is a problem on each edge!

Formally, the $i$-th edge on the tree directly connects vertex $u_i$ and $v_i$ and contains a math problem which belongs to $c_i$ category.

She makes a decision that she will**choose two endpoints $s, t$ and walk from $t$ to $s$** on each of next $m$ days. During her walk, she must solve all problems that she will go through, but unfortunately, not on all days she will be able to do that - because the problems may be too hard!

More precisely, Kazari is able to solve all categories of problems at the beginning of a day, however, once she solve a Hard problem, she will lose all her faith at once, in the rest of the day she is only able to solve Easy problems, i.e., if she is encountered with a Medium or Hard problem during this time, she will fail.

There is a piece of good news that on each morning of next $m$ days, exactly one problem will be chosen to become easier, i.e., a Hard problem will become a Medium problem, a Medium problem will become a Easy problem, a Easy problem will remain the same. Note that the effect is persistent.

Kazari would like to know, for each day,**whether she is able to reach $s$ from $t$** and **how many vertices from which she is able to reach $s$ among all $n$ vertices**.

In her opinion, all problems can be divided into three categories according to their difficulties - Easy, Medium and Hard, represented as $1, 2$ and $3$, respectively.

Today she goes to the forest and finds a strange tree with $n$ vertices: there is a problem on each edge!

Formally, the $i$-th edge on the tree directly connects vertex $u_i$ and $v_i$ and contains a math problem which belongs to $c_i$ category.

She makes a decision that she will

More precisely, Kazari is able to solve all categories of problems at the beginning of a day, however, once she solve a Hard problem, she will lose all her faith at once, in the rest of the day she is only able to solve Easy problems, i.e., if she is encountered with a Medium or Hard problem during this time, she will fail.

There is a piece of good news that on each morning of next $m$ days, exactly one problem will be chosen to become easier, i.e., a Hard problem will become a Medium problem, a Medium problem will become a Easy problem, a Easy problem will remain the same. Note that the effect is persistent.

Kazari would like to know, for each day,

The first line of the input contains an integer $T$ denoting the number of test cases.

Each test case starts with two integers $n, m$ $(1 \le n, m \le 10 ^ 5, \sum{n}, \sum{m} \le 3 \times 10 ^ 5)$ denoting the number of vertices and the number of days. Each of next $n - 1$ lines contains three integers $u_i, v_i, c_i$ $(1 \le u_i \neq v_i \le n, 1 \le c_i \le 3)$ describing an edge. Each of next $m$ lines contains four integers $a_i, b_i, s_i, t_i$ $(1 \le a_i \neq b_i \le n, 1 \le s_i, t_i \le n)$, $(a_i, b_i)$ represents the edge where the problem is chosen to become easier and $s_i, t_i$ represents the two endpoints that the girl chooses this day.

Each test case starts with two integers $n, m$ $(1 \le n, m \le 10 ^ 5, \sum{n}, \sum{m} \le 3 \times 10 ^ 5)$ denoting the number of vertices and the number of days. Each of next $n - 1$ lines contains three integers $u_i, v_i, c_i$ $(1 \le u_i \neq v_i \le n, 1 \le c_i \le 3)$ describing an edge. Each of next $m$ lines contains four integers $a_i, b_i, s_i, t_i$ $(1 \le a_i \neq b_i \le n, 1 \le s_i, t_i \le n)$, $(a_i, b_i)$ represents the edge where the problem is chosen to become easier and $s_i, t_i$ represents the two endpoints that the girl chooses this day.

提交代码