AT_abc305_e [ABC305E] Art Gallery on Graph

题目描述

### 题面 给定一张 $N$ 个点(编号为 $1 \sim N$),$M$ 条边的无向图,保证无重边无自环。现在有 $K$ 个被标记的点,其中第 $i$ 个被标记的点的编号为 $p_i$,任何从 $p_i$ 出发经过不超过 $h_i$ 条边能到达的点都会被染色(包括 $p_i$ 自身)。你需要求出这张图最终有哪些点被染色。

输入格式

第一行分别为 $N$ , $M$ , $K$ 。 接下来 $M$ 行,每行两个正整数 $a_i, b_i$ ,表示编号为 $a_i, b_i$ 的点连有一条无向边。 接着 $K$ 行,每行两个整数 $p_i$ , $h_i$ 表示编号为$p_i$ 的点将会从自己出发经过不超过 $h_i$ 条边进行染色。

输出格式

第一行一个数字 $G$,表示被染色的点的个数。 第二行 $G$ 个数字,表示被染色的点,按照从小到大的顺序输出。

说明/提示

$1 \le N \le 2 \times 10^5$,$0 \le M \le 2 \times 10^5$,$1 \le K,a_i,b_i,p_i,h_i \le N$,$p_i$ 互不相同。 保证给定的图无重边,无自环。