#P18236. Don't Detect Cycle

Don't Detect Cycle

Don't Detect Cycle

题目描述

有一个含有 NN 个顶点的无向图 GG,顶点编号为 1,2,…,N1,2,\ldots,N。最初图中没有边。

你需要向图中加入 MM 条预先给定的无向边。第 ii 条边连接 uiu_i 与 viv_i,称为边 ii。保证所有边加入后得到的图是简单图,即没有自环或重边。

请判断是否存在一个 1,2,…,M1,2,\ldots,M 的排列 P=(P1,P2,…,PM)P=(P_1,P_2,\ldots,P_M),使得可以按照以下规则加入全部边;若存在,请输出任意一个。

对于 i=1,2,…,Mi=1,2,\ldots,M,依次执行:

  1. 在加入边 PiP_i 之前,检查当前图。如果当前图中存在经过顶点 uPiu_{P_i} 或 vPiv_{P_i} 的环,则本次操作不合法,整个过程失败。
  2. 否则,将边 PiP_i 加入图中。

加入一条边之后可以产生环;只有之后再加入与已有环上顶点关联的边时,才会违反条件。一个顶点与某个环位于同一连通分量,并不意味着该顶点本身位于环上。

图不一定连通,可能包含孤立点。

共有 TT 组测试数据,请分别求解。

输入格式

第一行一个整数 TT。

每组测试数据第一行两个整数 N,MN,M。接下来 MM 行,每行两个整数 ui,viu_i,v_i,描述边 ii。

输出格式

对每组测试数据:

  • 如果不存在合法排列,输出一行 −1-1。
  • 否则,输出一行 MM 个以空格分隔的整数,表示一个合法排列。

有多个合法答案时,可以输出任意一个。

数据范围

所有输入均为整数。

  • 1≤T≤20001\le T\le2000。
  • 每组 2≤N≤40002\le N\le4000,1≤M≤40001\le M\le4000。
  • 1≤ui,vi≤N1\le u_i,v_i\le N。
  • 每组给定的图均为简单图。
  • 所有测试数据的 NN 之和不超过 40004000。
  • 所有测试数据的 MM 之和不超过 40004000。

样例 1

1
4 4
1 2
2 3
3 4
4 2
1 4 3 2

样例 1 说明

最终的图如下,边旁的数字表示边的编号。

样例1的图

按照 P=(1,2,3,4)P=(1,2,3,4) 加边也满足条件。以下两幅图按顺序展示从空图到加入全部边的过程。

依次加入边1和边2

继续加入边3和边4

但是,按 P=(2,3,4,1)P=(2,3,4,1) 加边时,前三条边已经形成经过顶点 22 的环,此时不能再加入边 11。

先加入边2和边3

边4形成环后不能再加入边1

P=(1,4,3,2)P=(1,4,3,2) 和 P=(2,4,1,3)P=(2,4,1,3) 也都是合法答案。

样例 2

4
4 5
1 2
2 3
3 4
3 1
1 4
5 3
1 2
2 3
3 4
9 10
3 5
1 8
5 8
4 9
6 7
7 9
1 2
1 4
2 4
4 6
8 10
1 4
3 8
2 5
3 4
1 5
5 8
2 8
5 7
4 5
3 7
-1
1 2 3
1 2 3 4 8 9 10 7 6 5
-1