← 返回题目列表

Codeforces · 1927/F

F. 微循环

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

给定一个具有 $$$n$$$ 个顶点和 $$$m$$$ 边的无向加权图。图中每对顶点之间至多有一条边,并且图中不包含环(从顶点到自身的边)。图不一定是连通的。

如果图中的环不两次经过相同的顶点并且不包含相同的边两次,则该环被称为简单环。

在此图中找到任何简单循环,其中最轻边的权重最小。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后按照测试用例的描述进行操作。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \le n \le m \le \min(\frac{n\cdot(n - 1)}{2}, 2 \cdot 10^5)$$$) - 图的大小和边的数量。

测试用例接下来的 $$$m$$$ 行包含三个整数 $$$u$$$、$$$v$$$ 和 $$$w$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$, $$$1 \le w \le 10^6$$$) — 顶点 $$$u$$$ 和$$$v$$$ 由权重 $$$w$$$ 的边连接。

保证每对顶点之间最多有一条边。请注意,在给定的约束下,图中始终至少存在一个简单循环。

保证所有测试用例的 $$$m$$$ 值之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一对数字 $$$b$$$ 和 $$$k$$$,其中:

- $$$b$$$ — 找到的循环中边的最小权重,
- $$$k$$$ — 找到的循环中的顶点数。

在下一行,输出从 $$$1$$$ 到 $$$n$$$ 的 $$$k$$$ 数字——按遍历顺序循环的顶点。

请注意,答案始终存在,因为在给定的约束下,图中始终至少存在一个简单循环。

示例

输入 #1

5
6 6
1 2 1
2 3 1
3 1 1
4 5 1
5 6 1
6 4 1
6 6
1 2 10
2 3 8
3 1 5
4 5 100
5 6 40
6 4 3
6 15
1 2 4
5 2 8
6 1 7
6 3 10
6 5 1
3 2 8
4 3 4
5 3 6
2 6 6
5 4 5
4 1 3
6 4 5
4 2 1
3 1 7
1 5 5
4 6
2 3 2
1 3 10
1 4 1
3 4 7
2 4 5
1 2 2
4 5
2 1 10
3 1 3
4 2 6
1 4 7
2 3 3

输出 #1

1 3
1 2 3 
3 3
6 4 5 
1 5
4 2 1 6 3 
1 4
1 4 3 2 
3 3
2 3 1