题目描述

Alice 知道 Bob 有一棵秘密的树（图论意义上的树），包含 $n$ 个节点和 $n - 1$ 条带权边，边权为 $[0, 2^{60} - 1]$ 内的整数。她知道树的结构，但不知道边权的具体信息。

多亏 Bob 良心发现，Alice 得到了 $m$ 条关于这棵树的结论。每条结论给出三个整数 $u, v$ 和 $val$，表示 $u$ 和 $v$ 之间唯一的最短路径上所有边权的 异或和（XOR） 等于 $val$。

给出的结论中可能存在错误，Alice 希望找出最大的整数 $W$，使得前 $W$ 条结论是兼容的。也就是说，至少存在一种边权分配方案能同时满足前 $W$ 条结论，但无法同时满足前 $W + 1$ 条结论（或者总共只给出了 $W$ 条结论）。

请帮助 Alice 求出 $W$ 的确切值。

输入格式

输入包含多组测试数据，第一行包含一个整数 $t$ ($1 \le t \le 5$)，表示测试数据的组数。请注意，原题 $t=30$，洛谷上拆为了 $6$ 个测试点评测。

对于每组数据，第一行包含两个整数 $n$ ($1 \le n \le 100000$) 和 $c$ ($1 \le c \le 100000$)，分别表示树的节点数量以及给出的结论数量。接下来的 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示树中连接第 $u$ 个节点和第 $v$ 个节点的一条边。接下来的 $c$ 行，每行提供一条结论，包含三个整数 $u$、$v$ 和 $val$，其中 $1 \le u, v \le n$，$val \in [0, 2^{60} - 1]$。

输出格式

对于每组测试数据，输出一行一个整数 $W$。

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

提示

翻译由 DeepSeek V4 Pro 完成