Skip to content

1341: 2-SAT

题目

题目描述

对于一系列形如 $(x_i=a) \lor (x_j=b)$ 的约束,其中 $a,b\in {0,1}$,你需要判断是否存在一组 ${x_i}$ 使其同时满足。如果有,请输出一组解。

Input

请从 stdin 读入。

第一行两个整数 $n, m (1 \leq n, m \leq 10 ^ 6)$,分别表示变量和约束的个数。

接下来$m$行,每行四个整数 $i, a, j, b$,表示有一条形如 $(x_i=a) \lor (x_j=b)$ 的约束。 例如 $1, 0, 2, 1$ 表示 $(x_1=0) \lor (x_2=1) $。

对于 $ 30$ 分的数据,$n \leq 3000$。

Output

请输出到 stdout 中。

输出第一行,如果这些约束可同时满足输出 Yes,否则输出 No

如果存在方案,请在第二行输出 $n$ 个空格隔开的整数,第 $i$ 个表示 $x_i$ 的取值。

如果存在多组解,输出任意一种即可。

Sample Input

txt 3 4 1 1 2 1 1 0 2 1 1 1 2 0 1 0 2 0

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

Sample Output

txt No

txt Yes 1 1 0

Constraints

Time Limit: 1s

Memory Limit: 256MB

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!