Ski optimization

Simone lives on the top of a very high, snowy mountain in northern Sweden. When Simone wants to go from her house on the top to some other place on the mountain, she can use a system of one-way lifts between some places.

Currently, for each place on the mountain there is exactly one lift which will take Simone to some other place on the mountain (she usually walks back home). However, this means that travelling takes a lot of time, since the number of lifts Simone may have to take from her home to her destination may be really large.

Recently, Simone got a large grant from the Swedish Association for Mountain Entertainment (SAME) to build more lifts on the mountain, to further enhance the mountains’ tourism. Simone doesn’t care much for tourism though, she just wants to be able to travel faster. In fact, she doesn’t want to have to travel using more than $K$ lifts from her house, regardless of her destination.

She wonders if her grant will cover this, and has thus asked you to compute the number of new lifts she must build.

Input

The first line of input contains two integers $2 \le N$ and $1 \le K$ – the number of locations on the mountain and maximum number of lifts Simone wants to use. The locations are numbered between $1$ to $N$, and her home has number $1$.

The following $N$ lines contains two integers $1 \le A \not= B \le N$, meaning that there is a lift taking Simone from location $A$ to location $B$.

Output

The first and only line of output should contain a single integer, the minimum number of lifts Simone must build.

Grading

Your solution will be graded on a number of subtasks. To get the points for a subtask, you must be accepted on all test cases in the subtask.

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

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

3