問題文

頂点に $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