P12204 [COI 2022] 委员选举 / Povierenstvo

译自 [HIO (COI) 2022](https://hsin.hr/hio2022/zadaci/) 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$ 个不同的整数，表示委员会成员编号（任意顺序）。

【样例解释】 **样例 $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$ | $33$ | 无额外限制 | > 备注：**奇间接生气环**定义为序列 $x_1, x_2, \dots, x_k$（$k$ 为奇数），使得对任意 $i$，$x_i$ 或 $x_{i+1}$ 中至少有一个让对方生气。