A7578. [ABC142F] Pure
编程题
普及+/提高
知识点
题目描述
给定一个有 $N$ 个顶点、$M$ 条边的有向图 $G$。
图中的顶点编号为 $1$ 到 $N$，第 $i$ 条边是从顶点 $A_i$ 指向顶点 $B_i$。
保证图中没有自环和重边。
请判断是否存在 $G$ 的一个诱导子图（见注释），使得该子图中所有顶点的入度和出度都为 $1$。
如果存在，请给出一个这样的例子。
注意，空图不计入答案。
图中的顶点编号为 $1$ 到 $N$，第 $i$ 条边是从顶点 $A_i$ 指向顶点 $B_i$。
保证图中没有自环和重边。
请判断是否存在 $G$ 的一个诱导子图（见注释），使得该子图中所有顶点的入度和出度都为 $1$。
如果存在，请给出一个这样的例子。
注意，空图不计入答案。
输入格式
输入按以下格式从标准输入读入。
> $N$ $M$
> $A_1$ $B_1$
> $A_2$ $B_2$
> $\vdots$
> $A_M$ $B_M$
> $N$ $M$
> $A_1$ $B_1$
> $A_2$ $B_2$
> $\vdots$
> $A_M$ $B_M$
输出格式
如果不存在满足条件的 $G$ 的诱导子图，输出
否则，输出如下格式的一个满足条件的 $G$ 的诱导子图：
> $K$ $v_1$ $v_2$ $\ldots$ $v_K$
其中，$K$ 表示顶点数，$\{v_1, v_2, \ldots, v_K\}$ 表示该诱导子图的顶点集合（顺序不限）。
如果存在多个满足条件的诱导子图，输出任意一个即可。
-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
说明/提示
### 注释
对于有向图 $G = (V, E)$，满足以下条件的有向图 $G' = (V', E')$ 被称为 $G$ 的诱导子图：
- $V'$ 是 $V$ 的（非空）子集。
- $E'$ 是所有端点都属于 $V'$ 的 $E$ 中的边的集合。
### 约束条件
- $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)$ 互不相同。
- 所有输入均为整数。
### 样例解释 1
顶点集合为 $\{1, 2, 4\}$ 的 $G$ 的诱导子图的边集合为 $\{(1, 2), (2, 4), (4, 1)\}$，所有顶点的入度和出度均为 $1$。
### 样例解释 2
不存在满足条件的 $G$ 的诱导子图。
对于有向图 $G = (V, E)$，满足以下条件的有向图 $G' = (V', E')$ 被称为 $G$ 的诱导子图：
- $V'$ 是 $V$ 的（非空）子集。
- $E'$ 是所有端点都属于 $V'$ 的 $E$ 中的边的集合。
### 约束条件
- $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)$ 互不相同。
- 所有输入均为整数。
### 样例解释 1
顶点集合为 $\{1, 2, 4\}$ 的 $G$ 的诱导子图的边集合为 $\{(1, 2), (2, 4), (4, 1)\}$，所有顶点的入度和出度均为 $1$。
### 样例解释 2
不存在满足条件的 $G$ 的诱导子图。