最近的黑色顶点

题目描述

给定一个具有 $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$ 的路径中所包含的最少边数。

输入格式

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

$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$ 的第 $i$ 个字符为 1;如果为白色,则为 0。

Yes $S$

如果存在多个解,可以输出任意一个。

样例

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

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$。

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

No

不存在满足条件的染色方案,所以输出 No。

1 0
0

Yes
1

数据范围

• $1 \le N \le 2000$
• $N-1 \le M \le \min\lbrace N(N-1)/2, 2000 \rbrace$
• $1 \le u_i, v_i \le N$
• $0 \le K \le N$
• $1 \le p_1 \lt p_2 \lt \cdots \lt p_K \le N$
• $0 \le d_i \le N$
• 给定的图是简单且连通的。
• 输入均为整数。

提示

答案不唯一,输出任意合法解即可。