诱导子图

题目描述

给定一个具有 $N$ 个顶点、$M$ 条边的有向图 $G$。

这个图的顶点编号为 $1$ 到 $N$，第 $i$ 条边从顶点 $A_i$ 指向顶点 $B_i$。

保证这个图没有自环和重边。

请判断是否存在 $G$ 的一个诱导子图（见注记），使得其中所有顶点的入度都为 $1$、出度都为 $1$， 如果存在，请给出其中的一个例子。

不过，空图不计算在内。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$:$
$A_M$ $B_M$

输出格式

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

$K$
$v_1$
$v_2$
: $v_K$

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

样例

4 5
1 2
2 3
2 4
4 1
4 3

3
1
2
4

顶点集合为 $\{1, 2, 4\}$ 的 $G$ 的诱导子图的边集合为 $\{(1, 2), (2, 4), (4, 1)\}$，所有顶点的入度都为 $1$、出度都为 $1$。

4 5
1 2
2 3
2 4
1 4
4 3

-1

不存在满足条件的 $G$ 的诱导子图。

6 9
1 2
2 3
3 4
4 5
5 6
5 1
5 2
6 1
6 2

4
2
3
4
5

数据范围

• $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)$ 对互不相同
• 所有输入均为整数

提示

对于有向图 $G = (V, E)$，满足以下条件的有向图 $G' = (V', E')$ 称为 $G$ 的诱导子图：

• $V'$ 是 $V$ 的（非空）子集。
• $E'$ 是包含 $E$ 中所有两个端点都属于 $V'$ 的边的集合。

答案不唯一，输出任意合法解即可。