[Ceoi2006]Link

时间限制:10s      空间限制:64MB

题目描述

给 N个点N 条边的有向图。 要求添最小的边,使得点1 到达其他所有点的最短路长度不超过K。


输入格式

The first line of input contains two integers N and K (2 ≤ N ≤ 500 000, 1 ≤ K ≤ 20 000) – the number of pages and the target maximum number of links to be followed. Each of the following N lines contains two different integers A and B (1 ≤ A, B ≤ N) meaning that the link on page A points to page B.


输出格式

The first and only line of output should contain a single integer, the minimum number of additional links required to make the website K-reachable.


样例输入

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 

样例输出

3

提示

one possible solution is to add the links 1→7, 1→14 and 14→10


题目来源

没有写明来源

Menuappsclose