AT_1_ttpc2024_1_a.Don't Detect Cycle

有一个图 $G$，由 $N$ 个顶点组成，顶点编号为 $1, 2, \ldots, N$。起初，图中没有任何边。

接下来，我们将向图中添加 $M$ 条无向边。图中最终的边是预先确定的：第 $i$ 条边 $(1 \le i \le M)$ 连接顶点 $u_i$ 和 $v_i$。我们称其为边 $i$。添加后的图确保是简单图。

现在，你要判断是否存在一种排列 $(P_1, P_2, \ldots, P_M)$ 满足以下条件，并如满足条件则给出这样的一个实例。

条件：

• 按照索引顺序为 $i = 1, 2, \ldots, M$，依次执行以下操作：
  1. 如果当前图中包含 $u_{P_i}$ 或 $v_{P_i}$ 的环存在，则立即停止操作，此时条件不成立。
  2. 在图中添加边 $P_i$（即连接顶点 $u_{P_i}$ 和 $v_{P_i}$ 的无向边）。

共给出 $T$ 个测试用例，请分别解决每个测试用例。

环的定义：图 $G$ 中的环是指满足以下条件的顶点序列 $(v_0, \dots, v_{L-1})$ 和边序列 $(e_0, \dots, e_{L-1})$：

• $L \ge 1$
• 若 $i \neq j$，则 $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$ 被称作简单图，是因为没有自环和多重边。

输入通过标准输入给出，格式如下：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每个 $\text{case}_i (1 \le i \le T)$ 对应一个测试用例，格式如下：

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

对于每个测试用例，如果存在满足条件的排列 $(P_1, P_2, \ldots, P_M)$，则输出这样一个排列，元素之间用空格隔开；如果不存在，则输出 -1。

• 输入中所有的数值均为整数。
• $1 \le T \le 2000$
• 每个测试用例满足：
  • $2 \le N \le 4000$
  • $1 \le M \le 4000$
  • $1 \le u_i, v_i \le N$ （$1 \le i \le M$）
  • 添加所有给定的边后，图为简单图。
• 每份输入文件中，所有测试用例 $N, M$ 总和不超过 $4000$。

部分评分

若仅回答满足以下条件的数据集，可获得 $30$ 分：

• $T \le 50$
• 每个测试用例满足：
  • $N \le 100$
  • $M \le 100$
• 每份输入文件中，所有测试用例 $N, M$ 总和不超过 $100$

示例说明 1

给定图如下图所示：

按顺序 $P = (1, 2, 3, 4)$ 添加边后，图为如下图、符合条件：

因此，1 2 3 4 是一个正确的输出方案。若按顺序 $P = (2, 3, 4, 1)$ 添加边，则在添加边 $1$ 时会形成包含顶点 $2$ 的环，故不满足条件：

另外，像 $P = (1, 4, 3, 2)$ 或 $P = (2, 4, 1, 3)$ 的排列也符合条件。

示例说明 2

如果不存在满足条件的排列 $P$，则请输出 -1。注意，图不一定连通。

本翻译由 AI 自动生成