Link-Cut Tree

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

A simple cycle is a subgraph that contains $k$ ($3 ≤ k ≤ n$) vertices $a_1, a_2, \cdots, a_k$ and $k$ edges, such that for every $1 ≤ i ≤ k$ there is an edge connecting $a_i$ and $a_{(i \bmod k)+1}$ in the subgraph. The length of a simple cycle is the sum of the lengths of its edges.

The first line contains an integer $T$, the number of test cases. Each test case is given as follows.

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

The next $m$ lines each contain two integers $u_i$ and $v_i$ ($1 ≤ u_i, v_i ≤ n$), the endpoints of the edge with length $2^i$. There are no self loops and no multiple edges. The graph is not necessarily connected.

The sum of $n$ over all test cases and the sum of $m$ over all test cases do not exceed $10^6$.

For each test case, print one line. If the graph has no simple cycle, print -1. Otherwise, print the indices of the edges in the simple cycle with the smallest length, in increasing order, separated by spaces. It can be shown that there is at most one such answer.

The first test case is shown below. The number beside each edge is its index (outside the parentheses) and its length (inside the parentheses). The simple cycle with the smallest length consists of edges $2$, $4$, $5$, and $6$, with length $2^2 + 2^4 + 2^5 + 2^6 = 116$.