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