← 返回题目列表

AtCoder · awc0024_b

B. 谣言的传播

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

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