QOJ.ac

QOJ

Time Limit: 0.5 s Memory Limit: 512 MB
Statistics

题目描述

有 $n$ 个布尔变量 $x_1,x_2,\cdots, x_n$。

有 $m$ 个限制,每个限制形如:$x_a = b \vee x_c = 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

子任务

对于所有数据,$1 \leq n \leq 10^5, 1 \leq m \leq 5 \times 10^5$。