P4782 [Template] 2-SAT

There are $n$ Boolean variables $x_1\sim x_n$, and $m$ constraints that must be satisfied. Each constraint has the form: “$x_i$ is `true` / `false` or $x_j$ is `true` / `false`”. For example, “$x_1$ is true or $x_3$ is false”, “$x_7$ is false or $x_2$ is false”. The goal of the 2-SAT problem is to assign a value to each variable so that all constraints are satisfied.

The first line contains two integers $n$ and $m$, with the meanings as described above. The next $m$ lines each contain four integers $i$, $a$, $j$, $b$, meaning “$x_i$ is $a$ or $x_j$ is $b” ($a, b\in \{0,1\}$).

If there is no solution, output `IMPOSSIBLE`. Otherwise output `POSSIBLE`, and on the next line output $n$ integers $x_1\sim x_n$ ($x_i\in\{0,1\}$), representing a constructed solution.

$1\leq n, m\leq 10^6$. The first $3$ test points check for small mistakes, and the remaining $5$ test points check efficiency. Since the testdata is generated randomly, it may contain tricky cases such as `10 0 10 0`, but the official solution written in the most standard way did not make mistakes. The hints about what each test point is checking are in the official solution. Translated by ChatGPT 5