题目描述

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

题目大意

题面

给定一张 $N$ 个点（编号为 $1 \sim N$），$M$ 条边的无向图，保证无重边无自环。现在有 $K$ 个被标记的点，其中第 $i$ 个被标记的点的编号为 $p_i$，任何从 $p_i$ 出发经过不超过 $h_i$ 条边能到达的点都会被染色（包括 $p_i$ 自身）。你需要求出这张图最终有哪些点被染色。

输入格式

第一行三个正整数 $N,M,K$，含义见题目描述。

接下来 $M$ 行，每行两个正整数 $a_i,b_i$，表示编号为 $a_i,b_i$ 的点连有一条无向边。

接下来 $K$ 行，每行两个正整数 $p_i,h_i$，含义见题目描述。

输出格式

第一行一个数字 $G$，表示被染色的点的个数。

第二行 $G$ 个数字，表示被染色的点，按照从小到大的顺序输出。

数据范围

$1 \le N \le 2 \times 10^5$，$0 \le M \le 2 \times 10^5$，$1 \le K,a_i,b_i,p_i,h_i \le N$，$p_i$ 互不相同。

保证给定的图无重边，无自环。

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

4
1 2 3 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

提示

制約

• $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

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