题目描述

有 $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
1 0 0

示例 1 说明

条件为「$x_1$ 为真 或 $x_3$ 为假」，输出的赋值 $x_1=1, x_2=0, x_3=0$ 满足该条件。

如果输出 1 1 1 或 0 0 0 等其它合法方案，也会被判定为正确（本题使用 Special Judge）。

输入示例 2

2 4
1 1 2 1
1 0 2 0
1 0 2 1
1 1 2 0

输出示例 2

IMPOSSIBLE

示例 2 说明

四个条件穷举了 $x_1, x_2$ 的所有 $4$ 种取值组合中应有的情况，但两两矛盾，无可行解。

约束条件

• $1 \le n, m \le 10^6$
• $1 \le i, j \le n$
• $a, b \in \{0, 1\}$
• 所有输入值均为整数

提示

• 答案不唯一时，输出任意合法解均被接受（Special Judge）。
• 注意数据规模较大，建议使用快速读入。