分数: 475 点
问题陈述
有一个简单的无向图 N 顶点和 M 边,其中顶点编号为 1 to N,边的编号从 1 to M。边缘 i 连接顶点 a_i 和顶点 b_i.
K 保安人员编号为 1 to 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 is 0,不大于 h_1 = 1。因此,顶点 1 受到保护。
- 顶点之间的距离 2 和顶点 p_1 = 1 is 1,不大于 h_1 = 1。因此,顶点 2 受到保护。
- 顶点之间的距离 3 和顶点 p_2 = 5 is 1,不大于 h_2 = 2。因此,顶点 3 受到保护。
- 顶点之间的距离 5 和顶点 p_1 = 1 is 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