1385: 【模板】2-SAT 问题

有 $n$ 个布尔变量 $x1$∼$xn$，另有 $m$ 个需要满足的条件，每个条件的形式都是 「$xi$ 为 true / false 或 $xj$为 true / false」。比如 「$x1$ 为真或 $x3$ 为假」、「$x7$ 为假或 $x2$ 为假」。

2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。

第一行两个整数 $n$ 和 $m$，意义如题面所述。

接下来 $m$ 行每行 $4$ 个整数 $i$, $a$, $j$, $b$，表示 「$xi$为 $a$ 或 $xj$ 为 $b$」($a,b\in \{0,1\}$)

如无解，输出 IMPOSSIBLE；

否则输出 POSSIBLE。

下一行 $n$ 个整数 $x1\sim xn,$$xi\in \{0,1\}$），表示构造出的解。

3 1
1 1 3 0

POSSIBLE
0 0 0