Link-Cut Tree

BaoBao는 방금 링크-컷 트리(link-cut tree)라는 자료구조로 그래프에서 사이클을 찾는 방법을 배웠고, 직접 써 보기로 했다. 정점이 $n$개, 간선이 $m$개인 무방향 그래프가 주어진다. $i$번째 간선의 길이는 $2^i$이다. BaoBao는 길이가 가장 짧은 단순 사이클을 찾아야 한다.

단순 사이클은 원래 그래프의 부분 그래프로, $k$개($3 ≤ k ≤ n$)의 정점 $a_1, a_2, \cdots, a_k$와 $k$개의 간선으로 이루어진다. 모든 $1 ≤ i ≤ k$에 대해 부분 그래프에 $a_i$와 $a_{(i \bmod k)+1}$을 잇는 간선이 있어야 한다. 사이클의 길이는 사이클에 포함된 간선 길이의 합이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 원래 그래프의 정점 수 $n$과 간선 수 $m$($3 ≤ n ≤ 10^5$, $1 ≤ m ≤ 10^5$)이 주어진다.

이어지는 $m$개의 줄 중 $i$번째 줄에는 길이가 $2^i$인 간선의 양 끝점 $u_i$, $v_i$($1 ≤ u_i, v_i ≤ n$)가 주어진다. 자기 루프와 중복 간선은 없다. 그래프가 연결되어 있지 않을 수도 있다.

모든 테스트 케이스의 $n$ 합과 $m$ 합은 각각 $10^6$을 넘지 않는다.

각 테스트 케이스마다 한 줄을 출력한다. 단순 사이클이 없으면 -1을 출력한다. 있으면 길이가 가장 짧은 사이클을 이루는 간선의 번호를 오름차순으로 공백으로 구분해 출력한다. 이런 답은 최대 하나뿐임이 알려져 있다.

첫 번째 테스트 케이스는 아래와 같다. 간선 옆의 숫자는 간선 번호(괄호 밖)와 길이(괄호 안)이다. 길이가 가장 짧은 사이클은 2, 4, 5, 6번 간선으로 이루어지며, 길이는 $2^2 + 2^4 + 2^5 + 2^6 = 116$이다.