9312 - 2-SAT问题

n 个布尔变量 x_1 \sim x_n,另有 m 个需要满足的条件,每个条件的形式都是 「x_itrue / falsex_jtrue / false」。比如 「x_1 为真或 x_3 为假」、「x_7 为假或 x_2 为假」。

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

输入

第一行两个整数 nm,意义如题面所述。

接下来 m 行每行 4 个整数 i, a, j, b,表示 「x_iax_jb」(a, b\in {0,1})

输出

如无解,输出 IMPOSSIBLE;否则输出 POSSIBLE

下一行 n 个整数 x_1\sim x_nx_i\in{0,1}),表示构造出的解。

样例

输入

3 1
1 1 3 0

输出

POSSIBLE
0 0 0

提示

1\leq n, m\leq 5×10^5

来源

模板

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题