← 返回题目列表

AtCoder · abc142_f

F. 纯

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

分数: 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