← 返回题目列表

AtCoder · agc002_b

B. 盒子和球

中文机器翻译题面 查看原题

问题陈述

我们有 N 盒子,已编号 1 通过 N。一开始,盒子 1 包含一个红球,其他每个盒子包含一个白球。

Snuke 将执行以下操作 M 操作,一一进行。在 i第次操作,他从盒子里随机挑选一个球 x_i,然后他把它放进盒子里 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 是空的,盒子 2 包含 1 个红球和 1 个白球,以及盒子 3 包含一个白球。

现在,考虑第二个操作。如果斯努克从盒子里取出红球 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