# Problem C. Problems on a Tree

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

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

## Description

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.

## Input

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.

## Output

For each test case, print two integers for each day, the first integer denotes whether the girl is able to reach $s$ and the second integer denotes the number of vertices from which she is able to reach $s$.

## Sample Input

1
6 5
1 2 3
2 3 3
1 4 3
3 5 3
2 6 3
2 6 1 5
3 5 2 4
2 3 4 4
2 3 2 4
1 2 6 2

## Sample Output

0 4
0 5
1 2
0 5
1 5

chendu

## Source

2018 Multi-University Training Contest 4