题目描述

$N$ 個の頂点と $M$ 本の辺からなる、単純（自己ループおよび多重辺を含まない）かつ連結な無向グラフが与えられます。
$i\ =\ 1,\ 2,\ \ldots,\ M$ について、$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結ぶ無向辺です。

各頂点を白または黒で塗る方法であって、下記の $2$ つの条件をともに満たすものが存在するかを判定し、存在する場合はその一例を示してください。

• $1$ 個以上の頂点が黒で塗られている。
• すべての $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 を出力せよ。
存在する場合は、下記の形式の通り、$1$ 行目に Yes と出力し、$2$ 行目に各頂点を塗る方法を表す文字列 $S$ を出力せよ。 ここで、$S$ は長さ $N$ の文字列であり、$i\ =\ 1,\ 2,\ \ldots,\ N$ について $S$ の $i$ 文字目は、頂点 $i$ を黒で塗るとき $1$ 、白で塗るとき $0$ である。

Yes $S$

答えが複数ある場合、どれを出力しても正解とみなされる。

题目大意

给一个 $N$ 个点 $M$ 条边的无向简单联通图和 $K$ 个限制，你需要将结点染成黑白两色满足所有限制，每个限制形如 $p_i,d_i$ 表示点 $p_i$ 距离最近的黑点的距离恰好等于 $d_i$，问是否存在染色方案，若存在给出任意一组解。

两点之间的距离定义为它们之间的最短路径上的边数。特别的，任何点到其自身的距离为 $0$。

$N\le2000,N-1 \le m \le \min\{n(n-1)/2,2000\},K \le N$

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

Yes
10100

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

No

1 0
0

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\ \lt\ p_2\ \lt\ \cdots\ \lt\ p_K\ \leq\ N$
• $0\ \leq\ d_i\ \leq\ N$
• 与えられるグラフは単純かつ連結
• 入力はすべて整数

Sample Explanation 1

例えば、頂点 $1,\ 3$ を黒に、頂点 $2,\ 4,\ 5$ を白に塗るという方法が、問題文中の条件を満たします。 実際、$i\ =\ 1,\ 2,\ 3,\ 4,\ 5$ について、頂点 $i$ と「黒で塗られた頂点のうち頂点 $i$ からの距離が最小であるもの」の距離を $A_i$ で表すと、 $(A_1,\ A_2,\ A_3,\ A_4,\ A_5)\ =\ (0,\ 1,\ 0,\ 1,\ 2)$ であり、特に、$A_1\ =\ 0,\ A_5\ =\ 2$ が成り立ちます。

Sample Explanation 2

問題文中の条件を満たすように各頂点を白または黒で塗る方法が存在しないため、No を出力します。