AT_abc299_e [ABC299E] Nearest Black Vertex

题目描述

给定一个包含 $N$ 个顶点和 $M$ 条边的无向图，该图是简单图（不包含自环和重边）且连通。
对于 $i = 1, 2, \ldots, M$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

请判断是否存在一种将每个顶点涂成白色或黑色的方法，使得同时满足以下两个条件，并在存在时给出一种方案。

• 至少有一个顶点被涂成黑色。
• 对于所有 $i = 1, 2, \ldots, K$，都满足以下条件：
  • 顶点 $p_i$ 到“所有被涂成黑色的顶点中，距离 $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，第二行输出一个长度为 $N$ 的字符串 $S$，表示每个顶点的涂色方案。对于 $i = 1, 2, \ldots, N$，若第 $i$ 个顶点被涂成黑色，则 $S$ 的第 $i$ 个字符为 $1$，若被涂成白色，则为 $0$。

Yes
$S$

如果有多种方案，输出任意一种均可。

输入输出样例 #1

输入 #1

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

输出 #1

Yes
10100

输入输出样例 #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

输入输出样例 #3

输入 #3

1 0
0

输出 #3

Yes
1

说明/提示

数据范围

• $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 < p_2 < \cdots < p_K \leq N$
• $0 \leq d_i \leq N$
• 给定的图是简单且连通的
• 所有输入均为整数

样例解释 1

例如，将顶点 $1, 3$ 涂成黑色，顶点 $2, 4, 5$ 涂成白色，就是一种满足题意的方案。实际上，对于 $i = 1, 2, 3, 4, 5$，用 $A_i$ 表示顶点 $i$ 到“所有黑色顶点中距离 $i$ 最近的顶点”的距离，则 $(A_1, A_2, A_3, A_4, A_5) = (0, 1, 0, 1, 2)$，特别地，$A_1 = 0, A_5 = 2$ 成立。

样例解释 2

不存在满足题意的涂色方法，因此输出 No。

由 ChatGPT 4.1 翻译