E - Nearest Black Vertex 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500 点

問題文

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 を結ぶパスの辺の本数としてあり得る最小値として定義されます。

制約

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

入力例 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

Score : 500 points

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges (a simple graph contains no self-loop and no multi-edges).
For i = 1, 2, \ldots, M, the i-th edge connects vertex u_i and vertex v_i bidirectionally.

Determine whether there is a way to paint each vertex black or white to satisfy both of the following conditions, and show one such way if it exists.

  • At least one vertex is painted black.
  • For every i = 1, 2, \ldots, K, the following holds:
    • the minimum distance between vertex p_i and a vertex painted black is exactly d_i.

Here, the distance between vertex u and vertex v is the minimum number of edges in a path connecting u and v.

Constraints

  • 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
  • The given graph is simple and connected.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

If there is no way to paint each vertex black or white to satisfy the conditions, print No.
Otherwise, print Yes in the first line, and a string S representing a coloring of the vertices in the second line, as shown below.
Here, S is a string of length N such that, for each i = 1, 2, \ldots, N, the i-th character of S is 1 if vertex i is painted black and 0 if white.

Yes
S

If multiple solutions exist, you may print any of them.

Sample Input 1

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

Sample Output 1

Yes
10100

One way to satisfy the conditions is to paint vertices 1, 3 black and vertices 2, 4, 5 white.
Indeed, for each i = 1, 2, 3, 4, 5, let A_i denote the minimum distance between vertex i and a vertex painted black, and we have (A_1, A_2, A_3, A_4, A_5) = (0, 1, 0, 1, 2), where A_1 = 0, A_5 = 2.

Sample Input 2

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

Sample Output 2

No

There is no way to satisfy the conditions by painting each vertex black or white, so you should print No.

Sample Input 3

1 0
0

Sample Output 3

Yes
1