P17267 [ICPC 2017 Urumqi R] A Possible Tree

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$.

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]$.

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