Problem Description

Alice knows that Bob has a secret tree (in terms of graph theory) with $n$ nodes with $n - 1$ weighted edges with integer values in $[0, 2^{60} - 1]$. She knows its structure but does not know the specific information about edge weights.

Thanks to the awakening of Bob’s conscience, Alice gets $m$ conclusions related to his tree. Each conclusion provides three integers $u, v$ and $val$ saying that the exclusive $OR (XOR)$ sum of edge weights in the unique shortest path between $u$ and $v$ is equal to $val$.

Some conclusions provided might be wrong and Alice wants to find the maximum number $W$ such that the first $W$ given conclusions are compatible. That is say that at least one allocation of edge weights satisfies the first $W$ conclusions all together but no way satisfies all the first $W + 1$ conclusions (or there are only $W$ conclusions provided in total).

Help Alice find the exact value of $W$.

Input Format

The input has several test cases and the first line contains an integer $t (1 \le t \le 30)$ which is the number of test cases.

For each case, the first line contains two integers $n (1 \le n \le 100000)$ and $c (1 \le c \le 100000)$ which are the number of nodes in the tree and the number of conclusions provided. Each of the following $n - 1$ lines contains two integers $u$ and $v (1 \le u, v \le n)$ indicating an edge in the tree between the $u$-th node and the $v$-th node. Each of the following $c$ lines provides a conclusion with three integers $u$, $v$ and $val$ where $1 \le u$, $v \le n$ and $val \in [0, 2^{60} - 1]$.

Output Format

For each test case, output the integer $W$ in a single line.

2
7 5
1 2
2 3
3 4
4 5
5 6
6 7
1 3 1
3 5 0
5 7 1
1 7 1
2 3 2
7 5
1 2
1 3
1 4
3 5  
3 6
3 7  
2 6 6
4 7 7
6 7 3
5 4 5
2 5 6

3
4