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 30$)，表示测试数据的组数。

对于每组数据，第一行包含两个整数 $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$。

样例

输入 1

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

输出 1

3
4