QOJ.ac

QOJ

Time Limit: 0.5 s Memory Limit: 512 MB
[+4]

# 997. 2-SAT 问题

Statistics

题目描述

n 个布尔变量 x1,x2,,xn

m 个限制,每个限制形如:xa=bxc=d

构造一组合法的取值方案,使得所有的限制都被满足。

输入格式

输入的第一行包含两个整数 n,m

接下来 m 行,每行四个整数 a,b,c,d

输出格式

若无解,输出一行 No

否则,首先输出一行 Yes。接下来输出一行 n 个整数,表示你的构造。

样例数据

样例 1 输入

3 3
1 0 2 0
2 1 3 1
3 0 1 0

样例 1 输出

Yes
0 0 1

样例 2 输入

4 6
1 0 2 0
1 0 3 0
2 0 3 0
1 1 2 1
1 1 3 1
2 1 3 1

样例 2 输出

No

子任务

对于所有数据,1n105,1m5×105