AtCoder Grand Contest 002

B - Box and Ball


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

N 個の箱があります。 箱は 1 から N まで番号が振られています。 最初、1 番目の箱には赤いボールが 1 個入っています。 また、2~N 番目の箱には白いボールが 1 個ずつ入っています。

高橋君は M 回の操作を順に行います。 i 回目の操作では、x_i 番目の箱から適当なボールを 1 個選び、それを y_i 番目の箱へ移します。

高橋君がすべての操作を終えた後、赤いボールが入っている可能性のある箱は何個か求めてください。

制約

  • 2≤N≤10^5
  • 1≤M≤10^5
  • 1≤x_i,y_i≤N
  • x_i≠y_i
  • i 回目の操作の直前、x_i 番目の箱には 1 個以上のボールが入っている。

入力

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

N M
x_1 y_1
:
x_M y_M

出力

高橋君がすべての操作を終えた後、赤いボールが入っている可能性のある箱は何個か出力せよ。


入力例1

3 2
1 2
2 3

出力例1

2

1 回目の操作の後、1 番目の箱にはボールが入っておらず、2 番目の箱には赤いボールと白いボールが 1 個ずつ入っており、3 番目の箱には白いボールが 1 個入っています。

2 回目の操作で赤いボールを選んだ場合、赤いボールは 3 番目の箱へ移ります。 2 回目の操作で白いボールを選んだ場合、赤いボールは 2 番目の箱に残ります。


入力例2

3 3
1 2
2 3
2 3

出力例2

1

すべてのボールが 3 番目の箱へ集まります。


入力例3

4 4
1 2
2 3
4 1
3 4

出力例3

3

Problem Statement

We have N boxes, numbered 1 through N. At first, box 1 contains one red ball, and each of the other boxes contains one white ball.

Snuke will perform the following M operations, one by one. In the i-th operation, he randomly picks one ball from box x_i, then he puts it into box y_i.

Find the number of boxes that may contain the red ball after all operations are performed.

Constraints

  • 2≤N≤10^5
  • 1≤M≤10^5
  • 1≤x_i,y_i≤N
  • x_i≠y_i
  • Just before the i-th operation is performed, box x_i contains at least 1 ball.

Input

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

N M
x_1 y_1
:
x_M y_M

Output

Print the number of boxes that may contain the red ball after all operations are performed.


Sample Input 1

3 2
1 2
2 3

Sample Output 1

2

Just after the first operation, box 1 is empty, box 2 contains one red ball and one white ball, and box 3 contains one white ball.

Now, consider the second operation. If Snuke picks the red ball from box 2, the red ball will go into box 3. If he picks the white ball instead, the red ball will stay in box 2. Thus, the number of boxes that may contain the red ball after all operations, is 2.


Sample Input 2

3 3
1 2
2 3
2 3

Sample Output 2

1

All balls will go into box 3.


Sample Input 3

4 4
1 2
2 3
4 1
3 4

Sample Output 3

3

Submit提出する