#P9666. [ICPC2021 Macao R] Link-Cut Tree

[ICPC2021 Macao R] Link-Cut Tree

题目描述

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 nn vertices and mm edges, where the length of the ii-th edge equals 2i2^i. She needs to find a simple cycle with the smallest length.

A simple cycle is a subgraph of the original graph containing kk (3kn3 \le k \le n) vertices a1,a2,,aka_1, a_2, \cdots, a_k and kk edges such that for all 1ik1 \le i \le k there is an edge connecting vertices aia_i and a(imodk)+1a_{(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 TT indicating the number of test cases. For each test case:

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

For the following mm lines, the ii-th line contains two integers uiu_i and viv_i (1ui,vin1 \le u_i, v_i \le n) indicating an edge connecting vertices uiu_i and viv_i with length 2i2^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 nn nor the sum of mm of all test cases will exceed 10610^6.

输出格式

For each test case output one line. If there are no simple cycles in the graph output -1 (without quotes); Otherwise output kk 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 得到一个有 nn 个点,mm 条边的无向图,其中第 ii 条边的权值为 2i2^i。她需要找到一个权值最小的环。

环是原图的子图,包含 kk (3kn3 \le k \le n) 个点 a1,a2,,aka_1, a_2, \cdots, a_kkk 条边,使得对于所有的 1ik1 \le i \le k ,子图中存在边连接点 aia_ia(imodk)+1a_{(i \mod k) + 1} 。环的权值为环上所有边的权值之和。

每一个测试点有多组测试数据。 第一行有一个整数 TT 表示数据组数。

第二行有两个整数 nnmm (3n1053 \le n \le 10^5, 1m1051 \le m \le 10^5),分别为点数和边数。

接下来 mm 行, 第 ii 行包括两个整数 uiu_iviv_i (1ui,vin1 \le u_i, v_i \le n) 表示有一条边连接 uiu_iviv_i ,权值为 2i2^i。 请注意,图 不一定 连通。

保证所有测试样例 nn 之和, mm 之和均不超过 10610^6.

对每一组测试数据输出一行。如果图中没有环,输出 -1 。 否则 升序 输出边的编号,共 kk 个整数 , 显然答案唯一。

第一个测试样例如图,图中标注出的为边的编号,环 22, 44, 55, 66 边权为 22+24+25+26=1162^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 22, 44, 55 and 66 with a length of 22+24+25+26=1162^2 + 2^4 + 2^5 + 2^6 = 116.