#5487. 「COI 2022」Povjerenstvo

题目描述

译自 $COI$ $2022$ $T3$「Povjerenstvo」

你知道为一个题目遴选委员会挑选成员有多难吗？不知道？那么你知道谁知道吗？当然是马尔纳先生。通过观察人际互动，无所不知的马尔纳先生已经确定了理想的委员会构成应该是怎样的。

共有 $N$ 个人被考虑加入委员会，并且记录了他们之间的 $M$ 种关系。一种关系由一个有序对 $(a, b)$ 描述，表示 $a$ 不喜欢 $b$。马尔纳先生将一个厌恶圈定义为一个由不同的人组成的序列 $x_{1}, x_{2}, \ldots, x_{k}$，其中对于每个 $1 \leq i \leq k$，人员 $x_{i}$ 不喜欢人员 $x_{i+1}$（并假设 $x_{k+1}=x_{1}$）。马尔纳先生注意到这群人有一个奇特的性质：不存在由奇数个人组成的厌恶圈。

为了最大限度地减少对委员会人选的不满，马尔纳先生正在寻找一个满足以下条件的委员会：委员会内的每个人都互相认可，而委员会外的每个人都庆幸自己不在其中。更准确地说：

1. 委员会内部不得有两人，其中一人不喜欢另一人。
2. 对于委员会外的每一个人，委员会中都应有至少一个人是他们所不喜欢的。

你能找到这样一群人吗？

输入格式

第一行包含正整数 $N$ 和 $M$，分别表示人数和他们之间的关系数量。

接下来的 $M$ 行中，第 $i$ 行包含一个有序对正整数 $a_{i}$ 和 $b_{i}$ ($1 \leq a_{i}, b_{i} \leq N$)，表示 $a_i$ 不喜欢 $b_i$。对于所有的 $i=1,2, \ldots M$，都有 $a_i \neq b_i$，且没有重复列出的有序对。

给定的关系将保证不存在由奇数个人组成的厌恶圈。

输出格式

如果无法选出满足给定条件的一群人，则在唯一的一行中输出 $-1$。

否则，在第一行输出一个正整数 $K$ ($1 \leq K \leq N$)，表示委员会中的人数。在下一行输出 $K$ 个不同的正整数 $p_{1}, p_{2}, \ldots p_{K}$ ($1 \leq p_{i} \leq N$)，即组成委员会的人员编号。

如果存在多种解，输出任意一种即可。

样例 1

输入

4 4
1 2
1 3
2 4
3 4

输出

2
4 1

第一个样例满足第一个子任务和第二个子任务的限制。

样例 2

输入

4 4
1 2
2 3
3 4
4 1

输出

2
1 3

第二个样例不满足第一个子任务的限制，但满足第二个子任务的限制。

样例 3

输入

8 11
1 2
2 1
3 4
4 5
5 6
6 3
7 8
8 7
3 2
7 3
8 1

输出

3
1 3 5

第三个样例既不满足第一个子任务的限制，也不满足第二个子任务的限制。

数据范围与提示

对于所有输入数据，满足 $1 \leq N \leq 500000$ 和 $0 \leq M \leq 500000$。

详细子任务附加限制及分值如下表所示：

子任务	分值	附加限制
1	$13$	不存在厌恶圈。
2	$21$	将所有关系视为无向边，所形成的图中不存在长度为奇数的圈。
3	$33$	$N, M \leq 5000$
4		无附加限制。