三位一体王国恰好有 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