分数: 100 点
问题陈述
你得到一个图 G 组成 N 顶点编号 1, 2, \ldots, N。最初, G 没有边缘。
你将添加 M 无向边到 G。图的最终形状是预先确定的,并且 i-要添加的边 (1 ≤ i ≤ M) 连接顶点 u_i 和 v_i。我们将其称为边 i.
保证生成的图将是简单图。
判断是否存在一种排列 (P_1, P_2, \ldots, P_M) of (1, 2, \ldots, M) 满足以下条件的排列,如果存在这样的排列,请给出一个示例。
条件
你必须能够将所有 M 边缘到 G 按照以下步骤添加:
- 对于 i = 1, 2, \dots, M,重复以下操作:
- 如果在 G 中已经存在包含任一顶点的环 u_{P_i} 或顶点 分别为 v_{P_i},则条件不满足,程序结束。
- 添加边 P_i (连接的无向边) u_{P_i} 和 v_{P_i}) 到 G.
你被给予 T 测试用例;解决它们中的每一个。
什么是循环?
一个循环在 G 被定义为一系列顶点 (v_0, \dots, v_{L - 1}) 和一系列边 (e_0, \dots, e_{L - 1}) 满足以下条件:
- L \ge 1
- i \neq j \implies v_i \neq v_j, e_i \neq e_j
- 对于 0 \le i \le L - 2,边缘 e_i 连接顶点 v_i 和 v_{i+1}
- 边缘 e_{L-1} 连接顶点 v_{L-1} 和 v_0
图是简单的是什么意思?
图表 G 如果图中不包含自环或多重边,则为简单图。约束
- 所有输入值均为整数。
- 1 \le T \le 2000
- 对于每个测试用例:
- 2 \le N \le 4000
- 1 \le M \le 4000
- 1 \le u_i, v_i \le N\ (1 ≤ i ≤ M)
- 通过添加所有给定边形成的图是简单图。
- 总和 N 所有测试用例最多 4000.
- 总和 M 所有测试用例最多 4000.
子任务
30 满足以下条件通过测试集将获得积分:
- T \le 50
- 对于每个测试用例:
- N \le 100
- M \le 100
- 总和 N 所有测试用例最多 100.
- 总和 M 所有测试用例最多 100.
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
在这里, \text{case}_i\ (1 ≤ i ≤ T) 代表 i- 第一个测试用例。每个测试用例均按以下格式给出:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
输出
对于每个测试用例,如果排列 (P_1, P_2, \ldots, P_M) 满足条件的存在,输出这样的 P ,用空格分隔。如果不存在这样的排列,输出 -1.
示例输入 1
1 4 4 1 2 2 3 3 4 4 2
示例输出 1
2 4 1 3
给定的图具有以下形状:

如果我们按顺序添加边 P = (1, 2, 3, 4),条件如下面所示得到满足:

因此, 1 2 3 4 是一个有效输出。
然而,如果我们按顺序添加边 P = (2, 3, 4, 1),在添加边之前会创建包含顶点 2 的环 1 可以被添加,因此条件不满足。

其他有效输出包括 P = (1, 4, 3, 2) or 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
示例输出 2
-1 3 2 1 4 10 2 8 7 9 6 5 3 1 -1
如果没有有效的 P 存在,输出 -1。注意,该图不一定是连通的。