← 返回题目列表

Codeforces · 1354/E

E. 图形着色

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

给你一个无向图,没有自环或多重边,由 $$$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. $$$|col_u - col_v| = 1$$$ 对于每条边 $$$(u, v)$$$,其中 $$$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$$$ 行包含边的描述:第 $$$i$$$ 行包含两个整数 $$$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”(不带引号)。

示例

输入 #1

6 3
2 2 2
3 1
5 4
2 5

输出 #1

YES
112323

输入 #2

5 9
0 2 3
1 2
1 3
1 5
2 3
2 4
2 5
3 4
3 5
4 5

输出 #2

NO