题目描述

BaoBao just learned how to use a data structure called link-cut tree to find cycles in a graph and decided to give it a try. BaoBao is given an undirected graph with $n$ vertices and $m$ edges, where the length of the $i$-th edge equals $2^i$. She needs to find a simple cycle with the smallest length.

A simple cycle is a subgraph of the original graph containing $k$ ($3 \le k \le n$) vertices $a_1, a_2, \cdots, a_k$ and $k$ edges such that for all $1 \le i \le k$ there is an edge connecting vertices $a_i$ and $a_{(i \mod k) + 1}$ in the subgraph. The length of a simple cycle is the total length of the edges in the cycle.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($3 \le n \le 10^5$, $1 \le m \le 10^5$) indicating the number of vertices and edges in the original graph.

For the following $m$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$) indicating an edge connecting vertices $u_i$ and $v_i$ with length $2^i$. There are no self loops nor multiple edges. Note that the graph is not necessarily connected.

It's guaranteed that neither the sum of $n$ nor the sum of $m$ of all test cases will exceed $10^6$.

输出格式

For each test case output one line. If there are no simple cycles in the graph output -1 (without quotes); Otherwise output $k$ integers separated by a space in increasing order indicating the indices of the edges in the simple cycle with the smallest length. It can be shown that there is at most one answer.

Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!

题目大意

BaoBao刚学会如何用一种叫做 LCT 的数据结构去找图中的环，因此决定试一试。BaoBao 得到一个有 $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$，为最小环。

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

2 4 5 6
-1

提示

The first sample test case is shown below. The integers beside the edges are their indices (outside the parentheses) and lengths (inside the parentheses). The simple cycle with the smallest length consists of edges $2$, $4$, $5$ and $6$ with a length of $2^2 + 2^4 + 2^5 + 2^6 = 116$.