#P18236. Don't Detect Cycle
Don't Detect Cycle
Don't Detect Cycle
题目描述
有一个含有 个顶点的无向图 ,顶点编号为 。最初图中没有边。
你需要向图中加入 条预先给定的无向边。第 条边连接 与 ,称为边 。保证所有边加入后得到的图是简单图,即没有自环或重边。
请判断是否存在一个 的排列 ,使得可以按照以下规则加入全部边;若存在,请输出任意一个。
对于 ,依次执行:
- 在加入边 之前,检查当前图。如果当前图中存在经过顶点 或 的环,则本次操作不合法,整个过程失败。
- 否则,将边 加入图中。
加入一条边之后可以产生环;只有之后再加入与已有环上顶点关联的边时,才会违反条件。一个顶点与某个环位于同一连通分量,并不意味着该顶点本身位于环上。
图不一定连通,可能包含孤立点。
共有 组测试数据,请分别求解。
输入格式
第一行一个整数 。
每组测试数据第一行两个整数 。接下来 行,每行两个整数 ,描述边 。
输出格式
对每组测试数据:
- 如果不存在合法排列,输出一行 。
- 否则,输出一行 个以空格分隔的整数,表示一个合法排列。
有多个合法答案时,可以输出任意一个。
数据范围
所有输入均为整数。
- 。
- 每组 ,。
- 。
- 每组给定的图均为简单图。
- 所有测试数据的 之和不超过 。
- 所有测试数据的 之和不超过 。
样例 1
1
4 4
1 2
2 3
3 4
4 2
1 4 3 2
样例 1 说明
最终的图如下,边旁的数字表示边的编号。

按照 加边也满足条件。以下两幅图按顺序展示从空图到加入全部边的过程。


但是,按 加边时,前三条边已经形成经过顶点 的环,此时不能再加入边 。


和 也都是合法答案。
样例 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