Pure

题目描述

给定一个有向图 $G$，它有 $N$ 个顶点和 $M$ 条边。
顶点编号为 $1$ 到 $N$，第 $i$ 条边是从顶点 $A_i$ 指向顶点 $B_i$。
保证图中没有自环或重边。 判断是否存在 $G$ 的一个诱导子图（见备注），使得每个顶点的入度和出度都为 $1$。如果存在，请给出一个这样的子图。
这里空图不被视为子图。

输入格式

输入按下列格式由标准输入给出： $N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_M$ $B_M$

输出格式

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

这表示顶点集为 $\{v_1, v_2, \ldots, v_K\}$ 的 $G$ 的诱导子图。($v_1, v_2, \ldots, v_K$ 的顺序任意。) 如果存在多个满足条件的子图，输出其中任意一个均可。

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

3
1
2
4

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

-1

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'$ 是 $G$ 的一个诱导子图：

$V'$ 是 $V$ 的一个（非空）子集。 $E'$ 是 $E$ 中所有两个端点都在 $V'$ 的边的集合。顶点集为 $\{1, 2, 4\}$ 的诱导子图的边集合为 $\{(1, 2), (2, 4), (4, 1)\}$。在该图中每个顶点的入度和出度均为 $1$。
不存在满足条件的诱导子图。

标签: AtCoder|abc142F

来源

AtCoder|abc142F