← 返回题目列表

AtCoder · abc299_e

H. 最近的黑色顶点

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

分数: 500 点

问题陈述

给你一个简单的连通无向图 N 顶点和 M 边(简单图不包含自环且不包含多边)。
对于 i = 1, 2, \ldots, M, i第一条边连接顶点 u_i 和顶点 v_i 双向。

确定是否有一种方法可以将每个顶点绘制为黑色或白色以满足以下两个条件,如果存在则显示一种这样的方法。

  • 至少一个顶点被涂成黑色。
  • 对于每个 i = 1, 2, \ldots, K,以下成立:
    • 顶点之间的最小距离 p_i 并且涂成黑色的顶点正好是 d_i.

这里,顶点之间的距离 u 和顶点 v 是连接路径中的最小边数 u 和 v.

约束

  • 1 \leq N \leq 2000
  • N-1 \leq M \leq \min\lbrace N(N-1)/2, 2000 \rbrace
  • 1 \leq u_i, v_i \leq N
  • 0 \leq K \leq N
  • 1 \leq p_1 \lt p_2 \lt \cdots \lt p_K \leq N
  • 0 \leq d_i \leq N
  • 给定的图很简单且连通。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M
K
p_1 d_1
p_2 d_2
\vdots
p_K d_K

输出

如果无法将每个顶点绘制为黑色或白色以满足条件,则打印 No.
否则,打印 第一行中的 Yes 和一个字符串 S 表示第二行顶点的着色,如下所示。
在这里, S 是一个长度为 N 这样,对于每个 i = 1, 2, \ldots, N, i- 第一个字符 S is 1 如果顶点 i 被漆成黑色并且 0 如果是白色。

Yes
S

如果存在多个解决方案,您可以打印其中任何一个。


示例输入 1

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

示例输出 1

Yes
10100

满足条件的一种方法是绘制顶点 1, 3 黑色和顶点 2, 4, 5 白色。
确实,对于每个 i = 1, 2, 3, 4, 5,让 A_i 表示顶点之间的最小距离 i 和一个涂成黑色的顶点,我们有 (A_1, A_2, A_3, A_4, A_5) = (0, 1, 0, 1, 2),其中 A_1 = 0, A_5 = 2.


示例输入 2

5 5
1 2
2 3
3 1
3 4
4 5
5
1 1
2 1
3 1
4 1
5 1

示例输出 2

No

通过将每个顶点绘制为黑色或白色无法满足条件,因此您应该打印 No.


示例输入 3

1 0
0

示例输出 3

Yes
1