E - Art Gallery on Graph Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 475 点

問題文

頂点に 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 を結ぶパスに含まれる辺の本数の最小値のことをいいます。

グラフに含まれる頂点のうち、警備されている頂点を 小さい方から順に 全て列挙してください。

制約

  • 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
  • 入力で与えられる値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

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

出力例 1

4
1 2 3 5

警備されている頂点は 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 は警備されている頂点です。

入力例 2

3 0 1
2 3

出力例 2

1
2

入力で与えられるグラフに辺がない場合もあります。

入力例 3

10 10 2
2 1
5 1
6 1
2 4
2 5
2 10
8 5
8 6
9 6
7 9
3 4
8 2

出力例 3

7
1 2 3 5 6 8 9

Score : 475 points

Problem Statement

There is a simple undirected graph with N vertices and M edges, where vertices are numbered from 1 to N, and edges are numbered from 1 to M. Edge i connects vertex a_i and vertex b_i.
K security guards numbered from 1 to K are on some vertices. Guard i is on vertex p_i and has a stamina of h_i. All p_i are distinct.

A vertex v is said to be guarded when the following condition is satisfied:

  • there is at least one guard i such that the distance between vertex v and vertex p_i is at most h_i.

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

List all guarded vertices in ascending order.

Constraints

  • 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
  • The given graph is simple.
  • 1 \leq p_i \leq N
  • All p_i are distinct.
  • 1 \leq h_i \leq N
  • All input values are integers.

Input

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

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

Output

Print the answer in the following format. Here,

  • G is the number of guarded vertices,
  • and v_1, v_2, \dots, v_G are the vertex numbers of the guarded vertices in ascending order.
G
v_1 v_2 \dots v_G

Sample Input 1

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

Sample Output 1

4
1 2 3 5

The guarded vertices are 1, 2, 3, 5.
These vertices are guarded because of the following reasons.

  • The distance between vertex 1 and vertex p_1 = 1 is 0, which is not greater than h_1 = 1. Thus, vertex 1 is guarded.
  • The distance between vertex 2 and vertex p_1 = 1 is 1, which is not greater than h_1 = 1. Thus, vertex 2 is guarded.
  • The distance between vertex 3 and vertex p_2 = 5 is 1, which is not greater than h_2 = 2. Thus, vertex 3 is guarded.
  • The distance between vertex 5 and vertex p_1 = 1 is 1, which is not greater than h_1 = 1. Thus, vertex 5 is guarded.

Sample Input 2

3 0 1
2 3

Sample Output 2

1
2

The given graph may have no edges.

Sample Input 3

10 10 2
2 1
5 1
6 1
2 4
2 5
2 10
8 5
8 6
9 6
7 9
3 4
8 2

Sample Output 3

7
1 2 3 5 6 8 9