B - Spread of Rumors Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

ある学校には N 人の生徒がおり、各生徒には 1 から N までの出席番号が付けられています。

あるとき、面白い噂が発生しました。最初の時点（すべてのグループワークが行われる前）では、出席番号 1, 2, \ldots, K の K 人の生徒だけがこの噂を知っており、それ以外の生徒は噂を知りません。

この学校では、今後 M 回のグループワークが 1 番目から M 番目まで順番に行われます。なお、異なるグループワークで同じペアが再び組まれることもあります。

i 番目 (1 \leq i \leq M) のグループワークでは、出席番号 A_i の生徒と出席番号 B_i の生徒がペアを組んで作業します。そのグループワークの開始時点でペアの2人のうち少なくとも一方が噂を知っていれば、そのグループワークの終了後には2人とも噂を知っている状態になります。どちらも噂を知らない場合は、何も変化しません。

あるグループワークによる噂の伝播は、それ以降のグループワークに影響します。

すべてのグループワークが終わった後に、噂を知っている生徒の人数を求めてください。

制約

  • 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
  • 1 行目には、生徒の人数を表す N 、グループワークの回数を表す M 、最初に噂を知っている生徒の人数を表す K が、スペース区切りで与えられる。
  • 2 行目から M + 1 行目では、各グループワークでペアを組む生徒の出席番号が与えられる。M = 0 の場合、この部分は存在しない。
  • 1 + i 行目 (1 \leq i \leq M) では、i 番目のグループワークでペアを組む生徒の出席番号 A_i と B_i がスペース区切りで与えられる。

出力

すべてのグループワークが終わった後に噂を知っている生徒の人数を 1 行で出力してください。

入力例 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

Score : 266 pts

Problem Statement

A school has N students, each assigned a student ID number from 1 to N.

At some point, an interesting rumor started. At the initial time (before any group work takes place), only the K students with student ID numbers 1, 2, \ldots, K know this rumor, and no other students know it.

From now on, M group work sessions will take place at this school, in order from the 1-st to the M-th. Note that the same pair may be paired together again in different group work sessions.

In the i-th (1 \leq i \leq M) group work session, the student with student ID A_i and the student with student ID B_i form a pair and work together. If at least one of the two paired students knows the rumor at the start of that group work session, then both students will know the rumor after that group work session ends. If neither of them knows the rumor, nothing changes.

The propagation of the rumor caused by a group work session affects all subsequent group work sessions.

Determine the number of students who know the rumor after all group work sessions have been completed.

Constraints

  • 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)
  • The same pair may be paired together again in different group work sessions
  • All input values are integers

Input

N M K
A_1 B_1
A_2 B_2
\vdots
A_M B_M
  • The first line contains N representing the number of students, M representing the number of group work sessions, and K representing the number of students who initially know the rumor, separated by spaces.
  • From the 2nd line to the (M + 1)-th line, the student ID numbers of the students who form a pair in each group work session are given. If M = 0, this part does not exist.
  • The (1 + i)-th line (1 \leq i \leq M) contains the student ID numbers A_i and B_i of the students who form a pair in the i-th group work session, separated by a space.

Output

Print in one line the number of students who know the rumor after all group work sessions have been completed.

Sample Input 1

5 3 1
1 2
2 3
4 5

Sample Output 1

3

Sample Input 2

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

Sample Output 2

5

Sample Input 3

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

Sample Output 3

9