AT_abc299_e [ABC299E] Nearest Black Vertex

[problemUrl]: https://atcoder.jp/contests/abc299/tasks/abc299_e $ 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 $ 答えが複数ある場合、どれを出力しても正解とみなされる。

### 制約 - $ 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` を出力します。