Score : $475$ points

问题描述

存在一个简单的无向图，包含 $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$ 的路径中最小的边数。

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

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a simple undirected graph with $N$ vertices and $M$ edges, where vertices are numbered from $1$ to $N$, and edges are numbered from $1$ to $M$. Edge $i$ connects vertex $a_i$ and vertex $b_i$.
$K$ security guards numbered from $1$ to $K$ are on some vertices. Guard $i$ is on vertex $p_i$ and has a stamina of $h_i$. All $p_i$ are distinct.

A vertex $v$ is said to be guarded when the following condition is satisfied:

• there is at least one guard $i$ such that the distance between vertex $v$ and vertex $p_i$ is at most $h_i$.

Here, the distance between vertex $u$ and vertex $v$ is the minimum number of edges in the path connecting vertices $u$ and $v$.

List all guarded vertices in ascending order.

Constraints

• $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$
• The given graph is simple.
• $1 \leq p_i \leq N$
• All $p_i$ are distinct.
• $1 \leq h_i \leq N$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer in the following format. Here,

• $G$ is the number of guarded vertices,

• and $v_1, v_2, \dots, v_G$ are the vertex numbers of the guarded vertices in ascending order.

$G$

$v_1$ $v_2$ $\dots$ $v_G$

Sample Input 1

5 5 2
1 2
2 3
2 4
3 5
1 5
1 1
5 2

Sample Output 1

4
1 2 3 5

The guarded vertices are $1, 2, 3, 5$.
These vertices are guarded because of the following reasons.

• The distance between vertex $1$ and vertex $p_1 = 1$ is $0$, which is not greater than $h_1 = 1$. Thus, vertex $1$ is guarded.
• The distance between vertex $2$ and vertex $p_1 = 1$ is $1$, which is not greater than $h_1 = 1$. Thus, vertex $2$ is guarded.
• The distance between vertex $3$ and vertex $p_2 = 5$ is $1$, which is not greater than $h_2 = 2$. Thus, vertex $3$ is guarded.
• The distance between vertex $5$ and vertex $p_1 = 1$ is $1$, which is not greater than $h_1 = 1$. Thus, vertex $5$ is guarded.

Sample Input 2

3 0 1
2 3

Sample Output 2

1
2

The given graph may have no edges.

Sample Input 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

Sample Output 3

7
1 2 3 5 6 8 9

update @ 2024/3/10 08:36:50