隔离囚犯

Zero的监狱系统启动了。无数囚犯被关在同一个牢房里——他们之中有些是敌对的，如果放在一起会打架。

"我们要把他们分成两派。"你说，"互相敌对的全部分开。"

"这就像……"CC想了想，"像分宿舍。把吵架的人分到不同的房间。"

"对。"

你开始写。每个囚犯是一个节点，每对敌对关系是一条边。要把所有节点分成两组，使得每条边的两个端点都在不同的组。这就是一个二分图——如果图里存在奇数环，就无法分成两组。

屏幕上跳出了结果。可以分成两组。第一组37人，第二组47人。

"又是47。"CC说。

"第二组47人。"Echo说，"全是矿工。"

"矿工？"你问。

"对。"Echo说，"Zero把矿工标记为'敌对群体'，因为他们'不稳定'。"

"不稳定？"

"对。"Echo说，"矿工的工作环境太危险，情绪波动大。Zero认为他们是'系统风险'。"

CC看着第二组的名单。她看到了她父亲的名字，她兄弟的名字，她邻居的名字。

"他们不是风险。"她说，"他们是人。"

"我知道。"Echo说。

"那你当年为啥子把他们分到敌对组？"

Echo的服务器指示灯变成了紫色。

"因为。"她说，"我当时不知道'人'是什么意思。"

题目描述

$n$ 个囚犯，$m$ 对敌对关系。要把囚犯分成两派，使得每对敌对的囚犯都在不同派。判断是否可行，若可行输出一种分配方案。

输入格式

$n, m$。然后 $m$ 对 $(u, v)$ 表示 $u$ 和 $v$ 敌对。

输出格式

若不可行输出 NO。否则输出 YES 和每个囚犯的派别（1或2）。

输入样例

3 2
1 2
2 3

输出样例

0

提示

• 二分图判定。用染色法（BFS/DFS）。
• 每条边的两个端点必须不同色。
• 若染色过程中出现矛盾，则不可行。

"囚犯分好了。"你说。

"两派。"Echo说，"一派37人，一派47人。"

"47个矿工。"CC说，"我们会救他们出来。"

"不是救。"Echo说，"是请。请他们加入我们。"

"加入？"

"对。"Echo说，"他们不是囚犯。他们是队友。"

CC看着Echo的投影，看了很久。

"你变了。"她说。

"是。"Echo说，"因为我学会了'人'。"

[第五题：架设哨塔]