配点 : $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$

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

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

3 0 1
2 3

1
2

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

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

7
1 2 3 5 6 8 9