Problem Description

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.

Input Format

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}$).

Output Format

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.

3 1
1 1 3 0

POSSIBLE
0 0 0

Hint

$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