← 返回题目列表

AtCoder · abc305_e

H. 图上的艺术画廊

中文机器翻译题面 查看原题

分数: 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