1519：和平委员会

题目描述

原题来自：POI 2001

根据宪法，Byteland 民主共和国的公众和平委员会应该在国会中通过立法程序来创立。不幸的是，由于某些党派代表之间的不和睦而使得这件事存在障碍。

此委员会必须满足下列条件：

1. 每个党派都在委员会中恰有 $1$ 个代表；
2. 如果 $2$ 个代表彼此厌恶，则他们不能都属于委员会。

每个党在议会中有 $2$ 个代表。代表从 $1$ 编号到 $2n$。编号为 $2i-1$ 和 $2i$ 的代表属于第 $i$ 个党派。

任务：写一程序读入党派的数量和关系不友好的代表对，计算决定建立和平委员会是否可能，若行，则列出委员会的成员表。

输入格式

第一行有两个非负整数 $n$ 和 $m$。他们各自表示：党派的数量 $n$ 和不友好的代表对 $m$。

接下来 $m$ 行，每行为一对整数 $a, b$，表示代表 $a, b$ 互相厌恶。

输出格式

如果不能创立委员会，则输出一行 NIE。若能够成立，则输出包括 $n$ 个整数，按升序写出，每行一个，这些数字为委员会中代表的编号。

如果委员会能以多种方法形成，程序可以只输出它们的某一个。

样例

样例输入 #1

3 2
1 3
2 4

样例输出 #1

1
4
5

样例解释 #1

• $n=3$ 个党派，代表编号为 $1,2$（党派1），$3,4$（党派2），$5,6$（党派3）。
• 不友好的代表对有 $m=2$：
  1. $1$ 和 $3$ 互相厌恶
  2. $2$ 和 $4$ 互相厌恶
• 需要从每个党派选一个代表，且互相厌恶的代表不能同时选。
• 一种可行方案：选 $1$（党派1）、$4$（党派2）、$5$（党派3）。
  • 检查：$1$ 和 $3$ 不都选（$3$ 未选），$2$ 和 $4$ 不都选（$2$ 未选）。
• 输出 $1$、$4$、$5$（升序，每行一个）。

数据范围

• $1 \le n \le 8000$
• $0 \le m \le 20000$
• $1 \le a < b \le 2n$

时空限制

• 时间限制：1000 ms
• 内存限制：131072 KB

注意：本题是 2-SAT 问题。对于每个党派 $i$，两个代表分别为 $2i-1$ 和 $2i$，必须选其中一个。对于每一对互相厌恶的代表 $a$ 和 $b$，表示不能同时选 $a$ 和 $b$，即 $\lnot (a \land b)$，等价于 $(\lnot a \lor \lnot b)$。将其转化为蕴含式：$a \to \lnot b$ 且 $b \to \lnot a$。建图后求强连通分量，如果某个党派的两个代表在同一个强连通分量中，则无解（输出 NIE）。否则，按照拓扑逆序选择代表（选择强连通分量编号小的代表对应的变量取值）。输出所选的代表编号。