最近,Vlad 被生成树迷住了,所以他的朋友们毫不犹豫地送了他一个由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成的连通加权无向图作为他的生日礼物。
Vlad 将生成树的 ority 定义为其所有权重的按位 OR,现在他感兴趣的是通过选择某个生成树可以实现的最小可能 ority。生成树是给定图的不包含环的连通子图。
换句话说,您希望保留 $$$n-1$$$ 边,以便图保持连通并且边的按位或权重尽可能小。你必须找到最小的按位或本身。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。
每个测试用例前面都写有一个空行。
后面跟着两个数字 $$$n$$$ 和 $$$m$$$ ($$$3 \le n \le 2 \cdot 10^5, n - 1 \le m \le 2 \cdot 10^5$$$) — 分别是图的顶点数和边数。
接下来的 $$$m$$$ 行包含边的描述。 $$$i$$$ 行包含三个数字 $$$v_i$$$、$$$u_i$$$ 和 $$$w_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$1 \le w_i \le 10^9$$$, $$$v_i \neq u_i$$$) — 边连接的顶点及其权重。
保证所有测试用例的总和 $$$m$$$ 和总和 $$$n$$$ 不超过 $$$2 \cdot 10^5$$$ 并且每个测试用例包含一个连通图。
输出
打印 $$$t$$$ 行,每一行都包含相应输入数据集的答案 - 最小可能的生成树数量。
示例
输入 #1
3 3 3 1 2 1 2 3 2 1 3 2 5 7 4 2 7 2 5 8 3 4 2 3 2 1 2 4 2 4 1 2 1 2 2 3 4 1 2 1 2 3 2 1 3 3 3 1 4
输出 #1
2 10 3
注意
第一个测试用例的图表。
这棵树的 Ority 等于 2 或 2 = 2 并且它是最小的。
不排除权重 $$$1$$$ 的边,数量为 1 或 2 = 3。