分数: 366 分
问题陈述
有 N 高桥学校的学生,编号为 1 to N. M 给出学生之间的友谊关系,其中 i第 好友关系表明该学生 u_i 和学生 v_i 彼此是朋友(友谊是双向的)。请注意,相同的友谊关系不会出现多次,并且没有学生会与自己成为朋友。
最初,仅 K 学生 C_1, C_2, \ldots, C_K 知道某个谣言。从这个初始状态开始,谣言按照以下规则一天天传播:
> 评价: 每天开始时,为每个还不知道谣言的学生统计他们当前知道谣言的朋友数量。如果这个数字至少是 T,该学生将在当天结束时重新了解到谣言。
>
> 同时更新: 如果多名学生在某一天新了解到该谣言,则他们会在当天结束时同时了解到该谣言。即使某个学生在一天结束时新了解到谣言,这也不影响当天其他学生的评价。
这个过程每天都会重复,直到没有新学生知道这个谣言。
确定最终知道该谣言的学生人数。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq K \leq N
- 1 \leq T \leq N
- 1 \leq C_i \leq N (1 \leq i \leq K)
- 全部 C_i 是不同的
- 1 \leq u_i < v_i \leq N (1 \leq i \leq M)
- 所有对 (u_i, v_i) 是不同的
- 所有输入值均为整数
输入
N M K T C_1 C_2 \ldots C_K u_1 v_1 u_2 v_2 \vdots u_M v_M
- 第一行包含学生人数 N, 好友数量 M,初步知道该谣言的学生人数 K,以及谣言传播所需的好友数量阈值 T,用空格分隔。
- 第二行包含学号 C_1, C_2, \ldots, C_K 最初知道谣言的人,以空格分隔。
- 从第三行到 (M + 2)第行, M 给出了友谊关系。
- 的 (2 + i)第行 (1 \leq i \leq M) 包含学生编号 u_i 和 v_i 的 i第一个好友关系,以空格分隔。
输出
在一行中打印传播收敛后知道谣言的学生数量。
示例输入 1
5 6 2 2 1 2 1 3 2 3 1 4 2 4 3 5 4 5
示例输出 1
5
示例输入 2
6 5 2 2 1 6 1 2 2 3 3 4 4 5 5 6
示例输出 2
2
示例输入 3
10 16 2 2 1 2 1 3 2 3 1 4 2 4 3 5 4 5 3 6 4 6 5 7 6 7 5 8 6 8 7 9 8 9 7 10 8 10
示例输出 3
10
示例输入 4
18 30 3 2 1 2 3 1 4 2 4 2 5 3 5 4 6 5 6 4 7 5 7 6 8 7 8 6 9 7 9 8 10 9 10 8 11 9 11 10 12 11 12 10 13 11 13 12 14 13 14 3 15 5 15 14 16 15 16 14 17 15 17 16 18 17 18
示例输出 4
18
示例输入 5
1 0 1 1 1
示例输出 5
1