CF1354E Graph Coloring

给定一个无自环、无重边的无向图，该图包含 $n$ 个顶点和 $m$ 条边。同时给定三个整数 $n_1$、$n_2$ 和 $n_3$。 你能否将每个顶点标记为数字 1、2 或 3，使得： 1. 每个顶点恰好被标记为 1、2 或 3 中的一个数字； 2. 标记为 1 的顶点总数恰好为 $n_1$； 3. 标记为 2 的顶点总数恰好为 $n_2$； 4. 标记为 3 的顶点总数恰好为 $n_3$； 5. 对于每条边 $(u, v)$，有 $|col_u - col_v| = 1$，其中 $col_x$ 表示顶点 $x$ 的标记。 如果存在多种合法的标记方案，输出任意一种即可。

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 5000$，$0 \le m \le 10^5$），表示图的顶点数和边数。 第二行包含三个整数 $n_1$、$n_2$ 和 $n_3$（$0 \le n_1, n_2, n_3 \le n$），分别表示标记为 1、2、3 的顶点数量。保证 $n_1 + n_2 + n_3 = n$。 接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$），表示第 $i$ 条边连接的两个顶点。保证图中没有自环和重边。

如果存在合法的标记方案，第一行输出 "YES"（不带引号）。第二行输出一个长度为 $n$ 的字符串，仅包含数字 1、2、3，第 $i$ 个字符表示第 $i$ 个顶点的标记。 如果不存在合法的标记方案，输出 "NO"（不带引号）。

由 ChatGPT 4.1 翻译