AT_abc305_e [ABC305E] Art Gallery on Graph

[problemUrl]: https://atcoder.jp/contests/abc305/tasks/abc305_e 頂点に $ 1 $ から $ N $ の、辺に $ 1 $ から $ M $ の番号がついた $ N $ 頂点 $ M $ 辺の単純無向グラフがあります。辺 $ i $ は頂点 $ a_i $ と頂点 $ b_i $ を結んでいます。 $ 1 $ から $ K $ までの番号がついた $ K $ 人の警備員が頂点上にいます。警備員 $ i $ は頂点 $ p_i $ にいて、体力は $ h_i $ です。ここで全ての $ p_i $ は互いに異なります。 頂点 $ v $ が次の条件を満たす時、頂点 $ v $ を **警備されている頂点** と呼びます。 - 頂点 $ v $ と頂点 $ p_i $ の距離が $ h_i $ 以下であるような警備員 $ i $ が少なくとも 1 人存在する。 ここで、頂点 $ u $ と頂点 $ v $ の距離とは、頂点 $ u $ と頂点 $ v $ を結ぶパスに含まれる辺の本数の最小値のことをいいます。 グラフに含まれる頂点のうち、警備されている頂点を **小さい方から順に** 全て列挙してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ \vdots $ $ a_M $ $ b_M $ $ p_1 $ $ h_1 $ $ p_2 $ $ h_2 $ $ \vdots $ $ p_K $ $ h_K $

答えを以下の形式で出力せよ。ここで、 - 警備されている頂点の個数を $ G $ 、 - 警備されている頂点の頂点番号を **昇順に** 並べたものを $ v_1,\ v_2,\ \dots,\ v_G $ と定義する。 > $ G $ $ v_1 $ $ v_2 $ $ \dots $ $ v_G $

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ M\ \leq\ \min\ \left(\frac{N(N-1)}{2},\ 2\ \times\ 10^5\ \right) $ - $ 1\ \leq\ K\ \leq\ N $ - $ 1\ \leq\ a_i,\ b_i\ \leq\ N $ - 入力で与えられるグラフは単純 - $ 1\ \leq\ p_i\ \leq\ N $ - $ p_i $ は互いに異なる - $ 1\ \leq\ h_i\ \leq\ N $ - 入力で与えられる値は全て整数 ### Sample Explanation 1 警備されている頂点は $ 1,\ 2,\ 3,\ 5 $ の $ 4 $ 頂点です。 これらの頂点が警備されている頂点である理由は以下の通りです。 - 頂点 $ 1 $ と頂点 $ p_1\ =\ 1 $ の距離は $ 0 $ で、これは $ h_1\ =\ 1 $ 以下です。よって頂点 $ 1 $ は警備されている頂点です。 - 頂点 $ 2 $ と頂点 $ p_1\ =\ 1 $ の距離は $ 1 $ で、これは $ h_1\ =\ 1 $ 以下です。よって頂点 $ 2 $ は警備されている頂点です。 - 頂点 $ 3 $ と頂点 $ p_2\ =\ 5 $ の距離は $ 1 $ で、これは $ h_2\ =\ 2 $ 以下です。よって頂点 $ 3 $ は警備されている頂点です。 - 頂点 $ 5 $ と頂点 $ p_1\ =\ 1 $ の距離は $ 1 $ で、これは $ h_1\ =\ 1 $ 以下です。よって頂点 $ 5 $ は警備されている頂点です。 ### Sample Explanation 2 入力で与えられるグラフに辺がない場合もあります。