分数: 600 点
问题陈述
给定的是一个有向图 G 与 N 顶点和 M 边缘。
顶点已编号 1 to N,以及 i第一条边从顶点定向 A_i 到顶点 B_i.
保证图不包含自环或重边。
判断是否存在以下归纳子图(见注释) G 使得每个顶点的入度和出度都是 1。如果答案是肯定的,请显示一个这样的子图。
这里空图不被视为子图。
注释
对于有向图 G = (V, E),我们称之为有向图 G' = (V', E') 满足以下条件的诱导子图 G:
- V' 是(非空)子集 V.
- E' 是所有边的集合 E 的两个端点都在 V'.
约束
- 1 \leq N \leq 1000
- 0 \leq M \leq 2000
- 1 \leq A_i,B_i \leq N
- A_i \neq B_i
- 所有对 (A_i, B_i) 是不同的。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 A_2 B_2 : A_M B_M
输出
如果没有归纳子图 G 满足条件,打印 -1。
否则,打印一个诱导子图
满足条件的 G ,格式如下:
K v_1 v_2 : v_K
这代表了导出的子图 G 与 K 顶点集为 \{v_1, v_2, \ldots, v_K\}。 (顺序为 v_1, v_2, \ldots, v_K 没关系。) 如果有多个子图 G 满足条件,打印其中任何一个都被接受。
示例输入 1
4 5 1 2 2 3 2 4 4 1 4 3
示例输出 1
3 1 2 4
的诱导子图 G 其顶点集是 \{1, 2, 4\} 已设置边缘 \{(1, 2), (2, 4), (4, 1)\}。该图中每个顶点的入度和出度都是 1.
示例输入 2
4 5 1 2 2 3 2 4 1 4 4 3
示例输出 2
-1
没有归纳子图 G 满足条件。
示例输入 3
6 9 1 2 2 3 3 4 4 5 5 6 5 1 5 2 6 1 6 2
示例输出 3
4 2 3 4 5