给你一个无向图,没有自环或多重边,由 $$$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