Codeforces Round 923 (Div. 3) |
---|
Закончено |
Дан неориентированный взвешенный граф из $$$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$$$, где:
В следующей строке выведите $$$k$$$ чисел от $$$1$$$ до $$$n$$$ — вершины цикла в порядке обхода.
Обратите внимание, что ответ всегда существует, так как при заданных ограничениях в графе всегда есть хотя бы один простой цикл.
56 61 2 12 3 13 1 14 5 15 6 16 4 16 61 2 102 3 83 1 54 5 1005 6 406 4 36 151 2 45 2 86 1 76 3 106 5 13 2 84 3 45 3 62 6 65 4 54 1 36 4 54 2 13 1 71 5 54 62 3 21 3 101 4 13 4 72 4 51 2 24 52 1 103 1 34 2 61 4 72 3 3
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
Название |
---|