配置

25组数据,传统型,没有SpecialJudge。

背景

NOIp 2012 Day2 T3 疫情控制

描述

H国有n个城市,编号1到n,1号城市是首都。H国的首都爆发了一种危害性极高的传染病,已经散播到了全国。

当局为了控制疫情,限制每个城市只有一条出城的道路(即有向道路),而且出城后不能直接回城,只能到达通向的城市。

这里假设走每条道路花费的时间均是1天。

现在首都的防疫站已经修建完毕,首都防疫站可以控制K天内从首都可以到达的所有城市。

现在国王请你来添加一些有向道路,请问至少添加几条有向道路才能完全地控制疫情?

输入格式

第一行两个正整数N和K,含义见描述。

接下来N行,每行两个正整数u和v,表示u到v有一条有向道路。

数据保证,每个城市只有一条连接出去的有向道路。

输出格式

一行输出,即最少需要增加的有向道路数量。

样例输入1

7 3
1 2
2 3
3 4
4 5
5 6
6 7
7 1

样例输出1

1

样例解释1

添加的有向道路是1 -> 5。

可以证明没有其他同优解。

样例输入输出2

比赛数据包\blockade_2\blockade_2.in和blockade_2.out

数据范围与约定

  • 对于20%的数据:n \leq 5000
  • 对于40%的数据:n\leq 100000
  • 对于100%的数据:2 \leq N \leq 500 000, 1 \leq K \leq 20 000