← 返回题目列表

Codeforces · 173/D

D. 代表

中文机器翻译题面 查看原题

三位一体王国恰好有 n = 3k 个城市。它们全部位于流经整个王国的特里西西皮河岸边。有些城市位于河的一侧,其余的城市都位于河的另一侧。

一些城市之间通过桥梁相连。每座桥梁都连接着河对岸的两个城市。任何两个城市之间最多只存在一座桥梁。

最近就任的特里斯坦三世国王正忙着在各个城市之间分配他的副手。总共有 k 名代表,国王希望委托他们每人控制 3 个城市。然而,不能委托任何副手管理由桥梁连接的城市——副手可以为自己的口袋收取过高的过桥费用,这对国王的声誉不利。

如果可能的话,帮助国王特里斯坦三世在城市之间分配代表。

输入

第一行包含两个整数 n 和 m — 城市和桥梁的数量(3 ≤ n < 105,n = 3k,0 ≤ m ≤ 105)。接下来的 m 行描述了桥梁。第 i 行包含两个整数 ai 和 bi — 第 i 座桥连接的城市数量 (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ i ≤ m)。

保证没有桥梁将一座城市与其自身相连,并且任何两个城市仅通过一座桥梁相连。

输出

如果无法按照要求的方式分配代表,请单行打印“NO”(不带引号)。

否则,在第一行打印“YES”(不带引号),并在第二行打印应该由哪个副手负责每个城市。第 i 个数字应该代表代表的编号(从 1 到 k),他应该负责输入中第 i 个城市 - 总共应该有 n 个数字。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

6 6
1 2
4 1
3 5
6 5
2 6
4 6

输出 #1

YES
1 2 1 2 2 1

输入 #2

3 1
1 2

输出 #2

NO