[AdditionalFile5288.zip](file://AdditionalFile5288.zip?type=additional_file)

#5288. 「PA 2015」Kontrmanifestacja

标签: 传统 | 时间限制: 4000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2015 Runda 5 Kontrmanifestacja

每年，比托维茨（Bitowice）都会举办 $P=NP$ 平等游行。这是一个活动，参与者认为对于任何语言 $L$，如果存在一个非确定性图灵机能在多项式步数内识别 $L$，那么也存在一个确定性图灵机能在多项式步数内识别该语言，他们通过游行向社会表达自己的观点。

往年的游行活动都很平静——参与者最多喊喊「3-SAT 很简单！」或者举着写有最新多项式「算法」伪代码的横幅，寻找哈密顿回路，这些举动并未引起路人的太大关注。今年，游行的组织者决定吸引比托维茨居民的注意，计划喊出更具震撼力的口号（如果 $P=NP$ 成立，这些口号在某种程度上是真实的，比如「我们的钱不安全！」和「我们的隐私受到威胁！」）。

比托维茨安全局（ABB）的官员担心，游行参与者传播的内容可能导致居民大规模从银行提款并删除他们在社交媒体上的账户，而这些账户是 ABB 用于监视民众的工具。简而言之，他们怀疑这可能导致比托维茨局势的不稳定。

为了防止这种不稳定，ABB 官员计划组织一场反示威活动，推广 $P \neq NP$ 的信念，同时和平地阻止游行的进行。ABB 打算在游行路线上的某个路口突然发起反示威。然而，$P=NP$ 平等游行的确切路线直到最后都保密，ABB 需要提前准备反示威地点。他们只收到线索，游行将从某个路口开始，经过若干条道路，最终返回起点。你的第一个任务是初步验证这条信息，即检查比托维茨的道路基础设施是否允许存在这样的路线。此外，特工们想知道是否存在某些路口，如果信息属实，游行路线必定会经过这些路口。他们请你找出所有这样的路口——他们将从中选择最合适的反示威地点（如果不存在这样的路口，ABB 将转而执行 B 计划）。

比托维茨有 $n$ 个路口，通过单向道路连接。由于游行中还包括机械车辆，我们假设游行只能按照道路的方向移动。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $m$ $(2 \leq n \leq 500000, 1 \leq m \leq 1000000)$，分别表示比托维茨的路口数量和道路数量。路口编号为从 $1$ 到 $n$ 的整数。

接下来的 $m$ 行描述比托维茨的道路：第 $i$ 行包含两个整数 $a_{i}$ 和 $b_{i}$ $(1 \leq a_{i}, b_{i} \leq n, a_{i} \neq b_{i})$，表示第 $i$ 条道路从编号为 $a_{i}$ 的路口通向编号为 $b_{i}$ 的路口。任何有序对 $(a_{i}, b_{i})$ 都不会重复。

输出格式

如果无法组织游行，使其路线符合 ABB 掌握的信息，则输出 NIE。

否则，输出两行。第一行包含一个数字 $k$，表示游行路线必定经过的路口数量。第二行包含 $k$ 个数字，按升序排列，表示这些路口的编号（如果 $k=0$，则第二行留空）。

样例 1

输入

4 5
1 2
2 3
3 1
3 4
4 2

输出

2
2 3

样例 2

输入

3 2
1 2
2 3

输出

NIE