← 返回题目列表

AtCoder · awc0092_c

C. 谣言的传播

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

分数: 366 分

问题陈述

高桥是某学校的学生会长。在文化节筹备期间,他需要向学生们传达一个重要的通知。

有 N 该学校的学生,每个学生都被分配了一个编号 1 to N.

M 对同学之间的友谊关系给出。友谊是双向的,不存在自循环或多重边缘。

高桥最初选择 K 学生并直接告知他们。设数字为 K 最初被告知的学生是 S_1, S_2, \ldots, S_K.

信息通过友谊关系陆续传播。也就是说,知道该信息的学生的朋友也会学习该信息,并进一步传播给他们的朋友,等等。更准确地说,可以从任何学生联系到的所有学生 S_1, S_2, \ldots, S_K 通过关注零个或多个友谊边最终将学到信息。

求最终知道该信息的学生人数。请注意, K 最初获悉该信息的学生也算作知晓该信息的学生。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq S_i \leq N (1 \leq i \leq K)
  • S_i \neq S_j (i \neq j)
  • 1 \leq u_i < v_i \leq N (1 \leq i \leq M)
  • (u_i, v_i) \neq (u_j, v_j) (i \neq j)
  • 所有输入值均为整数

输入

N M K
S_1 S_2 \ldots S_K
u_1 v_1
u_2 v_2
\vdots
u_M v_M
  • 第一行包含 N 代表学生人数, M 代表好友数量,以及 K 代表最初通知的学生人数,以空格分隔。
  • 第二行包含数字 S_1, S_2, \ldots, S_K 的同学初步告知,用空格隔开。
  • 从第三行到 (M + 2)第行, M 友谊被放弃 M 行。
  • 的 (2 + i)第行 (1 \leq i \leq M) 包含数字 u_i 和 v_i 的两名学生 i第-个友谊,以空格分隔。这种友谊是双向的。每条边都以满足的形式给出 u_i < v_i.

输出

在一行中输出最终知道该信息的学生数量。


示例输入 1

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

示例输出 1

5

示例输入 2

8 5 2
1 6
1 2
2 3
3 4
6 7
7 8

示例输出 2

7

示例输入 3

10 7 3
1 5 9
1 2
2 3
3 4
5 6
7 8
8 10
9 10

示例输出 3

10