问题陈述
我们有 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