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 \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 翻译