图上的美术馆

题目描述

有一个 $N$ 个顶点、$M$ 条边的简单无向图,顶点编号为 $1$ 到 $N$,边编号为 $1$ 到 $M$。第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。

有 $K$ 名编号为 $1$ 到 $K$ 的保安位于某些顶点上。保安 $i$ 位于顶点 $p_i$,体力为 $h_i$。所有 $p_i$ 互不相同。

当满足以下条件时,称顶点 $v$ 被守护:

存在至少一名保安 $i$,使得顶点 $v$ 与顶点 $p_i$ 之间的距离不超过 $h_i$。

这里,顶点 $u$ 与顶点 $v$ 之间的距离是连接这两个顶点的路径中边数的最小值。

按升序列出所有被守护的顶点。

输入格式

输入按以下格式从标准输入给出:

N M K
a_1 b_1
a_2 b_2
⋮
a_M b_M
p_1 h_1
p_2 h_2
⋮
p_K h_K

输出格式

按以下格式输出答案。这里,

$G$ 是被守护顶点的个数,

$v_1, v_2, \dots, v_G$ 是被守护顶点的编号,按升序排列。

G
v_1 v_2 … 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$。

这些顶点被守护的原因如下。

顶点 $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

数据范围

• $1 \le N \le 2 \times 10^5$
• $0 \le M \le \min \left(\frac{N(N-1)}{2}, 2 \times 10^5 \right)$
• $1 \le K \le N$
• $1 \le a_i, b_i \le N$
• 给定的图是简单图。
• $1 \le p_i \le N$
• 所有 $p_i$ 互不相同。
• $1 \le h_i \le N$
• 所有输入值均为整数。