当前没有测试数据。

题目描述

有一个简单无向图，有$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$之间的距离是连接顶点$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$

示例1

输入：

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

示例2

输入：

3 0 1 2 3

输出：

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

输出：

7 1 2 3 5 6 8 9