题目描述

给定一个有 $N$ 个顶点和 $M$ 条边的有向图 $G$。
顶点编号从 $1$ 到 $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$
• 输入中的所有值都是整数。

输入格式

从标准输入读取输入数据，输入格式如下：

$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$ 的诱导子图，其中顶点集为 $\\{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