A - Spread of Rumors Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君のクラスには N 人の生徒がいます。各生徒には 0 から N - 1 までの出席番号が割り振られています。最初、出席番号 0 の生徒だけがある噂を知っています。

噂は、それを知っている生徒が別の生徒に直接伝えることで広まります。噂の伝達に関する記録が M 件与えられ、i 番目の記録 (a_i, b_i) は「出席番号 a_i の生徒が出席番号 b_i の生徒に噂を伝えようとした」ことを表します。

記録は i = 1, 2, \ldots, M の順に処理されます。i 番目の記録を処理するとき、出席番号 a_i の生徒がその時点で噂を知っていれば、出席番号 b_i の生徒も噂を知っている状態になります（すでに知っている場合は何も変わりません）。出席番号 a_i の生徒がその時点で噂を知らなければ、この記録では何も起こりません。

ある記録によって新たに噂を知った生徒は、それ以降の記録において噂を伝える側になることができます。

全ての記録を処理した後、最終的に噂を知っている生徒の人数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 10^5
  • 0 \leq a_i \leq N - 1
  • 0 \leq b_i \leq N - 1
  • a_i \neq b_i
  • 同じ (a_i, b_i) の組が複数回現れることがある
  • 入力はすべて整数である

入力

入力は以下の形式で与えられます。

N M
a_1 b_1
a_2 b_2
\vdots
a_M b_M

1 行目には、生徒の人数 N と伝達記録の件数 M がスペース区切りで与えられます。続く M 行の i 行目には、i 番目の伝達記録を表す 2 つの整数 a_i, b_i がスペース区切りで与えられます。

出力

最終的に噂を知っている生徒の人数を 1 行で出力してください。

入力例 1

4 3
0 1
1 2
3 2

出力例 1

3

入力例 2

4 3
1 2
0 1
2 3

出力例 2

2

入力例 3

8 13
0 3
2 4
3 2
4 5
5 1
1 7
6 7
7 6
0 2
2 4
4 5
5 6
6 7

出力例 3

7

入力例 4

15 28
0 4
1 2
4 1
2 3
3 5
6 7
5 6
8 9
7 8
10 11
11 12
12 13
13 14
0 10
9 10
14 2
4 6
6 1
1 9
9 11
11 13
13 12
12 14
14 5
5 6
6 7
7 8
8 9

出力例 4

13

入力例 5

1 0

出力例 5

1

Score : 266 pts

Problem Statement

There are N students in Takahashi's class. Each student is assigned an attendance number from 0 to N - 1. Initially, only the student with attendance number 0 knows a certain rumor.

The rumor spreads when a student who knows it directly tells it to another student. You are given M records of rumor transmission attempts. The i-th record (a_i, b_i) means "the student with attendance number a_i attempted to tell the rumor to the student with attendance number b_i."

The records are processed in order i = 1, 2, \ldots, M. When processing the i-th record, if the student with attendance number a_i knows the rumor at that point, then the student with attendance number b_i also comes to know the rumor (if they already know it, nothing changes). If the student with attendance number a_i does not know the rumor at that point, nothing happens for this record.

A student who newly learns the rumor from a certain record can become a transmitter of the rumor in subsequent records.

After processing all records, find the total number of students who know the rumor.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 10^5
  • 0 \leq a_i \leq N - 1
  • 0 \leq b_i \leq N - 1
  • a_i \neq b_i
  • The same pair (a_i, b_i) may appear multiple times
  • All input values are integers

Input

The input is given in the following format.

N M
a_1 b_1
a_2 b_2
\vdots
a_M b_M

The first line contains the number of students N and the number of transmission records M, separated by a space. The i-th of the following M lines contains two integers a_i and b_i representing the i-th transmission record, separated by a space.

Output

Output the number of students who know the rumor in the end, on a single line.

Sample Input 1

4 3
0 1
1 2
3 2

Sample Output 1

3

Sample Input 2

4 3
1 2
0 1
2 3

Sample Output 2

2

Sample Input 3

8 13
0 3
2 4
3 2
4 5
5 1
1 7
6 7
7 6
0 2
2 4
4 5
5 6
6 7

Sample Output 3

7

Sample Input 4

15 28
0 4
1 2
4 1
2 3
3 5
6 7
5 6
8 9
7 8
10 11
11 12
12 13
13 14
0 10
9 10
14 2
4 6
6 1
1 9
9 11
11 13
13 12
12 14
14 5
5 6
6 7
7 8
8 9

Sample Output 4

13

Sample Input 5

1 0

Sample Output 5

1