分数: 266 分
问题陈述
学校有 N 学生,每人分配一个学生 ID 号,来自 1 to N.
在某个时候,一个有趣的谣言开始了。在最初的时间(在进行任何小组工作之前),只有 K 有学生证号的学生 1, 2, \ldots, K 知道这个传闻,没有其他同学知道。
从现在开始, M 小组工作会议将在这所学校举行,按顺序从 1-st 到 M-th。请注意,同一对可能会在不同的小组工作会议中再次配对。
在 i-th (1 \leq i \leq M) 小组作业环节,持学生证的学生 A_i 和持有学生证的学生 B_i 结成一对并一起工作。如果两个配对的学生中至少有一个在小组作业开始时知道谣言,那么两个学生都会在小组作业结束后知道谣言。如果他们都不知道谣言,那么什么都不会改变。
一次小组工作会议引起的谣言传播会影响所有后续小组工作会议。
确定所有小组作业结束后知道谣言的学生人数。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq K \leq N
- 1 \leq A_i < B_i \leq N (1 \leq i \leq M)
- 同一对可能会在不同的小组工作会议中再次配对在一起
- 所有输入值均为整数
输入
N M K A_1 B_1 A_2 B_2 \vdots A_M B_M
- 第一行包含 N 代表学生人数, M 代表小组工作会议的数量,以及 K 代表最初知道该谣言的学生数量,以空格分隔。
- 从第 2 行到 (M + 1)第行,给出了每次小组作业中配对的学生的学生ID号。如果 M = 0,这部分不存在。
- 的 (1 + i)第行 (1 \leq i \leq M) 包含学生 ID 号 A_i 和 B_i 中结对的学生 i第组工作会议,以空格分隔。
输出
在一行中打印出所有小组作业完成后知道谣言的学生人数。
示例输入 1
5 3 1 1 2 2 3 4 5
示例输出 1
3
示例输入 2
8 5 2 3 5 2 4 4 6 5 6 7 8
示例输出 2
5
示例输入 3
10 8 3 1 4 4 7 7 10 5 6 2 5 5 6 8 9 6 8
示例输出 3
9