Informatica Online Judge

  Box and Ball [1774 / 06EE]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 30   Total Tried : 33


The Champion of this Problem (C++) : gs16036 - ms / 381byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

첫 번째 상자에 빨간색 공이 1개 들어 있고 나머지 $N-1$개의 상자에 흰색 공이 1개씩 들어 있는 박스 $N$개가 있다.

경곽이는 $X_i$ 번째 박스에 있는 공 하나를 $Y_i$번째 박스로 옮기는 $M$개의 연산을 차례대로 수행한다.

모든 작업이 완료되었을 때 빨간색 공을 포함하고 있는 가능성이 있는 박스의 총 수를 구해라.

Input

첫 줄에 박스의 수를 나타내는 정수 $N$과 연산의 수 $M$이 입력된다.

두 번째 부터 $M$줄에 걸쳐 연산이 입력 된다.

[입력값의 정의역]

$2≤ N ≤ 100,000$
$1≤ M ≤ 100,000$
$1≤ x_i, y_i ≤ 100,000$
$x_i≠y_i$

Output

모든 작업이 완료된 후 빨간색 공을 포함하고 있는 가능성이 있는 총 박스의 수를 출력한다.

IO Example

입력1
3 2
1 2
2 3

출력1
2



설명1:
첫 번째 작업 후 박스 1은 비게 되며 박스2는 빨간색+흰색, 박스 3은 흰색의 상태가 된다. 2번째 연산에서 흰색 또는 빨간색 공이 3번째 박스로 옮겨질 수 있으며 따라서 빨간색이 있을 수 있는 총 경우의 수는 2가 된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]