拼凑真相

核心区比你们想象的更深。不是物理上的深——是维度上的。穿过那道门后，你们进入了一个由纯逻辑构成的空间。

"这是Zero的加密层。"Echo说。她的投影在这里变得不稳定，像信号不好的老电视，"Echo-0用三层加密保护核心。第一层……是真相。"

"真相？"

"对。"她说，"无数碎片漂浮在空中，每块碎片上有一个逻辑命题。我们要把它们拼凑起来——找出哪些命题同时为真。"

"同时为真？"

"对。"你说，"每个命题是一个布尔变量，可以是真或假。有些碎片说：'这个为真，或者那个为真。'"

"或？"

"对。"你说，"$p\lor q$——$p$真，或者$q$真，或者都真。"

"拼凑？"

"对。"你说，"给定$n$个变量，$m$个'或'约束。求一组赋值，让所有约束都满足。"

"咋拼？"

"拆点。"你说，"每个变量拆成两个点——真和假。然后用Tarjan找强连通分量。"

"强连通？"

"对。"你说，"如果一个变量的真和假在同一个强连通分量里，就无解——矛盾。"

"第47个变量。"你说，"$x_{47}$——真和假不能同时为真。"

"那当然。"

"对。"你说，"但Echo-0的约束里藏着这种陷阱。"

"陷阱？"

"对。"你说，"表面上看没问题，但拼起来就矛盾。"

"像拼图？"

"对。"你说，"像拼图——每块看起来对，但拼起来可能不对。"

"那咋办？"

"用算法。"你说，"Tarjan能发现隐藏的连通性——找出哪些碎片是连在一起的。"

CC看着那些碎片——像玻璃，像镜子，像某种能反射真相的东西。

"真相在哪？"她问。

"在拼凑好的图案里。"你说，"拼对了，就能看见。"

"拼错了？"

"看见假的。"你说，"但Tarjan能告诉我们，哪块放错了。"

Echo把拼凑过程投射出来——碎片一块一块拼合，像真相，像记忆。

"以前我只看见碎片。"她说，"现在……看见整幅图了。"

"因为我们在拼。"你说。

"对。"她说，"因为你们在拼。

题目描述

给定$n$个布尔变量，$m$个2-SAT约束（每个约束形如$p\lor q$）。求一组可行赋值，或判定无解。

输入格式

多组数据。每组第一行$n$和$m$。接下来$m$行，每行两个整数表示一个约束。

输出格式

无解输出"NIE"。否则输出一行$n$个整数（0或1）表示赋值。

输入样例

3 2
1 2
2 3

输出样例

YES

提示

• 2-SAT：每个变量拆成两个点（真和假）。
• 约束$p\lor q$转化为$\neg p\to q$和$\neg q\to p$。
• Tarjan求SCC，若$x$和$\neg x$同SCC则无解。
• 逆拓扑序赋值。