题目背景

译自 HIO (COI) 2022 T3。

题目描述

给定 $N$ 个人和 $M$ 个有向关系，每个关系形如 $(a, b)$，表示 $b$ 会使 $a$ 生气。要求选出一个委员会满足以下条件：

• 委员会中任意两人之间没有直接生气关系；
• 对于不在委员会中的每个人，至少存在一个委员会成员使其生气。

特别地，题目保证图中不存在奇数长度的生气环。

一个生气环定义为序列 $x_1 \to x_2 \to \cdots \to x_k \to x_1$，其中 $x_{i+1}$ 使 $x_i$ 生气（$x_{k+1} = x_1$）。

请构造一个符合条件的委员会，或判断其不存在。

输入格式

• 第一行：两个整数 $N$ 和 $M$，表示人数和关系数。
• 接下来 $M$ 行：每行两个整数 $a_i, b_i$，表示一个关系 $(a_i, b_i)$。保证 $a_i \neq b_i$，且无重复关系。

输出格式

• 若无解，输出 $-1$。
• 若有解：
  • 第一行输出委员会人数 $K$。
  • 第二行输出 $K$ 个不同的整数，表示委员会成员编号（任意顺序）。

4 4
1 2
1 3
2 4
3 4

2
4 1 

4 4
1 2
2 3
3 4
4 1

2
1 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$：

委员会 $\{1,4\}$ 满足：

• 内部无冲突（$1$ 和 $4$ 之间无关系）。
• 对于外部人员 $2$ 和 $3$，$4$ 使 $2$ 生气，$1$ 使 $3$ 生气。

样例 $2$：

委员会 $\{1,3\}$ 满足：

• 内部无冲突。
• 外部人员 $2$ 被 $1$ 控制，$4$ 被 $3$ 控制。

【数据规模与约定】

对于所有数据，满足： $1 \leq N \leq 5 \times 10^5, \ 0 \leq M \leq 5 \times 10^5$。

子任务	分值	特殊条件
$1$	$13$	图中无任何生气环
$2$	$21$	图中无奇间接生气环（见备注）
$3$	$33$	$N, M \leq 5000$
$4$		无额外限制

备注：奇间接生气环定义为序列 $x_1, x_2, \dots, x_k$（$k$ 为奇数），使得对任意 $i$，$x_i$ 或 $x_{i+1}$ 中至少有一个让对方生气。