#ABC142F. Pure
Pure
题目描述
Given is a directed graph with vertices and edges.
The vertices are numbered to , and the -th edge is directed from Vertex to Vertex .
It is guaranteed that the graph contains no self-loops or multiple edges.
Determine whether there exists an induced subgraph (see Notes) of such that the in-degree and out-degree of every vertex are both . If the answer is yes, show one such subgraph.
Here the null graph is not considered as a subgraph.
给定的有向图 有 个顶点和 条边。
顶点的编号是 到 , 条边是从顶点 到顶点 的。
保证该图不包含自循环或多条边。
判断是否存在 的诱导子图(见注释),使得每个顶点的入度和出度都是 。如果答案是肯定的,请展示一个这样的子图。
这里不将空图视为子图。
输入格式
输入内容按以下格式标准输入:
输出格式
如果 没有满足条件的诱导子图,则打印 -1
。否则,打印满足条件的 的诱导子图,格式如下:
$K$
$v_1$
$v_2$
:
$v_K$
这表示有 个顶点的 的诱导子图,其顶点集合为 。(如果有多个满足条件的 子图,则接受打印其中任何一个。
样例 #1
样例输入 #1
4 5
1 2
2 3
2 4
4 1
4 3
样例输出 #1
3
1
2
4
样例 #2
样例输入 #2
4 5
1 2
2 3
2 4
1 4
4 3
样例输出 #2
-1
样例 #3
样例输入 #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
说明
对于有向图 ,我们称满足以下条件的有向图 为 的诱导子图:
- 是 的(非空)子集。
- 是 中所有端点都在 中的边的集合。
数据规模与约定
- 所有成对的 都是不同的。
- 输入的所有值都是整数。
样例 解释
顶点集为 的 的诱导子图的边集是 。该图中每个顶点的入度和出度都是 。
样例 解释
没有满足条件的诱导子图。