【模板】2-SAT

题目描述

有 $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\}$),表示构造出的解。

输入输出样例

输入样例 #1

3 1
1 1 3 0

输出样例 #1

POSSIBLE
0 0 0

说明

$1\leq n, m\leq 10^6$ , 前 $3$ 个点卡小错误,后面 $5$ 个点卡效率。 由于数据随机生成,可能会含有( 10 0 10 0)之类的坑,但按照最常规写法的写的标程没有出错,各个数据点卡什么的提示在标程里。