← 返回题目列表

AtCoder · ttpc2024_1_a

A. 不检测循环

中文机器翻译题面 查看原题

分数: 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,重复以下操作:
    1. 如果在 G 中已经存在包含任一顶点的环 u_{P_i} 或顶点 分别为 v_{P_i},则条件不满足,程序结束。
    2. 添加边 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。注意,该图不一定是连通的。