OI题库

网站管理员Kirk要给学校的网站改版。网站内有大量的网页，而且内容都很好，但是他注意到这些页面都没有被真确的链接。事实上，每个页面都包含一个确切的链接，链接到站内的其他页面。

这是一个不好的设计----从主页开始，访问者不得不在访问了很多页面之后才能找到他感兴趣的页面，而且有些页面可能从主页开始都访问不到。第一步，他想要加上几个链接使得所有页面都能够很快的从主页开始被访问到。新连接可以再站内的任意位置添加。 站点的N个页面被从1到N标记起来，主页被标记为1. 当然也有N个链接， 每个页面包含一个链接指向其他某个页面。
对于一个整数K，如果这个站点的每个页面（除了主页）从主页开始访问至多K个连接就能被访问到，就说这个站点是K可达的。
写一个程序，给出了网站的描述和一个整数K，找出使网站K可达所需要添加的链接的最少数目。

输入数据第一行包含两个整数N和K(2<=N<=500000 ,1<=K<=20 000) ，分别表示网页数和目标被连接的最大连接数。
接下来N行每行两个不同的整数A和B（1<=A,B<=N），表示链接从页面A链接到页面B。

输出只有一行，一个整数，表示使网站K可达所需额外添加的最少页面数。

样例输入1:

8 3
1 2
2 3
3 5
4 5
5 6
6 7
7 8
8 5
样例输出1:
2

样例输入2:

14 4
1 2
2 3
3 4
4 5
7 5
5 6
6 3
8 10
10 9
9 8
14 13
13 12
12 11
11 14

样例输出2:
3