← 返回题目列表

Codeforces · 1624/G

G. 小树

中文机器翻译题面 查看原题

最近,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。