P9666 [ICPC 2021 Macao R] Link-Cut Tree

宝宝刚刚学会使用一种称为“链接切割树”的数据结构来寻找图中的环，并决定尝试一下。宝宝得到一个有 $n$ 个顶点和 $m$ 条边的无向图，其中第 $i$ 条边的长度为 $2^i$。她需要找到一个长度最小的简单环。 一个简单环是原始图的一个子图，包含 $k$ ($3 \le k \le n$) 个顶点 $a_1, a_2, \cdots, a_k$ 和 $k$ 条边，使得对于所有 $1 \le i \le k$，在子图中存在一条边连接顶点 $a_i$ 和 $a_{(i \mod k) + 1}$。简单环的长度是环中边的总长度。

输入包含多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例： 第一行包含两个整数 $n$ 和 $m$ ($3 \le n \le 10^5$, $1 \le m \le 10^5$)，表示原始图中的顶点数和边数。 接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)，表示连接顶点 $u_i$ 和 $v_i$ 的一条边，其长度为 $2^i$。没有自环或重边。注意，图不一定是连通的。 保证所有测试用例中 $n$ 的总和和 $m$ 的总和都不会超过 $10^6$。

对于每个测试用例输出一行。如果图中没有简单环，则输出“-1”（不带引号）；否则输出 $k$ 个以空格分隔的整数，按升序表示简单环中最小长度的边的索引。可以证明最多只有一个答案。 请不要在每行末尾输出多余的空格，否则您的解答可能会被视为不正确！

第一个样例测试用例如下。边旁边的整数是它们的索引（括号外）和长度（括号内）。长度最小的简单环由边 $2$、$4$、$5$ 和 $6$ 组成，其长度为 $2^2 + 2^4 + 2^5 + 2^6 = 116$。 题面翻译由 ChatGPT-4o 提供。