9312 - 2-SAT问题
时间限制 : 1 秒
内存限制 : 128 MB
有 n 个布尔变量 x_1 \sim x_n，另有 m 个需要满足的条件，每个条件的形式都是 「x_i 为 true / false 或 x_j 为 true / false」。比如 「x_1 为真或 x_3 为假」、「x_7 为假或 x_2 为假」。
2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。
输入
第一行两个整数 n 和 m，意义如题面所述。
接下来 m 行每行 4 个整数 i, a, j, b，表示 「x_i 为 a 或 x_j 为 b」(a, b\in {0,1})
输出
如无解，输出 IMPOSSIBLE；否则输出 POSSIBLE。
下一行 n 个整数 x_1\sim x_n（x_i\in{0,1}），表示构造出的解。
样例
输入
3 1 1 1 3 0
输出
POSSIBLE 0 0 0
提示
1\leq n, m\leq 5×10^5 。
来源
模板