← 返回题目
题库练习 [ABC142F] Pure
← 上一题 下一题 →

A7578 | [ABC142F] Pure

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

给定一个有 $N$ 个顶点、$M$ 条边的有向图 $G$。
图中的顶点编号为 $1$ 到 $N$，第 $i$ 条边是从顶点 $A_i$ 指向顶点 $B_i$。
保证图中没有自环和重边。

请判断是否存在 $G$ 的一个诱导子图（见注释），使得该子图中所有顶点的入度和出度都为 $1$。
如果存在，请给出一个这样的例子。
注意，空图不计入答案。

输入格式

输入按以下格式从标准输入读入。

> $N$ $M$
> $A_1$ $B_1$
> $A_2$ $B_2$
> $\vdots$
> $A_M$ $B_M$

输出格式

如果不存在满足条件的 $G$ 的诱导子图，输出 -1。
否则，输出如下格式的一个满足条件的 $G$ 的诱导子图：

> $K$ $v_1$ $v_2$ $\ldots$ $v_K$

其中，$K$ 表示顶点数，$\{v_1, v_2, \ldots, v_K\}$ 表示该诱导子图的顶点集合（顺序不限）。
如果存在多个满足条件的诱导子图，输出任意一个即可。

输入输出样例

输入 #1
4 5
1 2
2 3
2 4
4 1
4 3
输出 #1
3
1
2
4
输入 #2
4 5
1 2
2 3
2 4
1 4
4 3
输出 #2
-1
输入 #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
C++ 编辑器
输入
输出