问题描述

给定一个简单的无向图，具有$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$的路径中边的最小数量。

按照升序列出所有受到保护的顶点。

约束条件

• $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$。
这些顶点之所以受到保护，是因为以下原因：

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