C - Straw Millionaire Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

アイテム 1 からアイテム N までの N 種類のアイテムがあります。はじめ、高橋君はアイテム 1 のみ持っています。

高橋君には M 人の友達がいます。i 人目 (1\le i\le M) の友達にアイテム A_i を渡すと、アイテム B_i をもらうことができます。

高橋君が手に入れることのできるアイテムはアイテム 1 を含めて何種類あるか求めてください。

制約

  • 2\le N\le 3\times 10^5
  • 1\le M\le 3\times 10^5
  • 1\le A_i,B_i\le N
  • A_i \neq B_i
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

答えを出力せよ。

入力例 1

5 5
1 2
2 3
3 4
2 4
5 2

出力例 1

4

例えば、以下のように行動することでアイテム 4 を手に入れることができます。

  • アイテム 1 を 1 人目の友達に渡す。アイテム 2 をもらう。
  • アイテム 2 を 4 人目の友達に渡す。アイテム 4 をもらう。

高橋君が手に入れられるアイテムはアイテム 1,2,3,4 の 4 種類です。したがって、4 を出力してください。

入力例 2

3 2
2 1
3 2

出力例 2

1

高橋君が手に入れられるアイテムはアイテム 1 の 1 種類です。

入力例 3

7 8
2 6
2 5
3 6
1 6
1 2
5 6
2 3
3 7

出力例 3

6

Score : 300 points

Problem Statement

There are N types of items item 1 through item N. Initially, Takahashi has only item 1.

He has M friends. If he gives item A_i to the i-th friend (1\le i\le M), he will receive item B_i.

Find how many types of items he can obtain, including item 1.

Constraints

  • 2\le N\le 3\times 10^5
  • 1\le M\le 3\times 10^5
  • 1\le A_i,B_i\le N
  • A_i \neq B_i
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

Output the answer.

Sample Input 1

5 5
1 2
2 3
3 4
2 4
5 2

Sample Output 1

4

For example, Takahashi can obtain item 4 by acting as follows:

  • Give item 1 to the first friend. Receive item 2.
  • Give item 2 to the fourth friend. Receive item 4.

He can obtain four types of items: items 1,2,3,4. Thus, output 4.

Sample Input 2

3 2
2 1
3 2

Sample Output 2

1

He can obtain one type of item: item 1.

Sample Input 3

7 8
2 6
2 5
3 6
1 6
1 2
5 6
2 3
3 7

Sample Output 3

6