CF173D Deputies

“三一王国”有恰好 $n=3k$ 座城市。所有城市都沿着特里西西皮河建造，这条河贯穿整个王国。一些城市在河的一侧，其余城市则在另一侧。 有些城市之间建有桥梁。每座桥只连接在河两岸的两座城市。任意两座城市之间最多只能有一座桥。 刚刚登基的特里斯坦三世国王正忙于将自己的副官分派到各城市，总共有 $k$ 位副官，国王希望让每位副官管理恰好三座城市。然而，任何一位副官都不能负责两座由桥梁连接的城市——因为副官可能会提高过桥费用谋取私利，这对国王的声誉不利。 请你帮特里斯坦三世分配副官管理城市，使得满足上述要求。如果无法实现请指出。

第一行包含两个整数 $n$ 和 $m$，分别表示城市数和桥的数目（$3 \leq n < 10^5$，$n=3k$，$0 \leq m \leq 10^5$）。接下来的 $m$ 行描述各桥，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$，表示第 $i$ 座桥连接的两座城市编号（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$，$1 \leq i \leq m$）。 保证没有桥连接同一座城市，且任意两座城市之间最多只有一座桥。

如果无法实现分配，输出一行 "NO"（不带引号）。 否则，第一行输出 "YES"（不带引号），第二行输出每座城市应由哪位副官管理的编号（从 $1$ 到 $k$ 之间的整数），第 $i$ 个数字表示编号为 $i$ 的城市应由哪位副官管理。应该总共输出 $n$ 个数。 如果存在多种方案，任选其一输出。

由 ChatGPT 5 翻译