Mini March Coding Challenge 2014

Esdeath

Esdeath is excited — she has information that Tatsumi will be appearing in one of N cities, conveniently labeled from 1 to N. There are exactly N−1 bidirectional roads connecting the cities, and all cities are connected to every other city by exactly one path. Because Esdeath does not want Tatsumi to escape unnoticed, she has brought her army in to wait for him. Esdeath's army has S soldiers, and she would like to station the soldiers at S of the N cities, such that no matter which city Tatsumi appears in, the minimum distance from any soldier to Tatsumi will be no greater than D roads. As one of Esdeath's pets, you'll be rewarded if you can help her find the minimum value of D — so do so, and quickly!

Input

The first line of input has 2 integers, N and S (1 ≤ S ≤ N ≤ 5000), the number of cities and the number of soldiers in Esdeath's army, respectively. Each of the next N−1 lines contain two integers u_i and v_i, representing a bidirectional road between cities u_i and v_i.

The following additional constraints will apply.

• At least 15% of the marks will be for test cases where N ≤ 100 and S = 1;
• At least 30% of the marks will be for test cases where N ≤ 100 and S ≤ 5;
• At least 50% of the marks will be for test cases where N ≤ 250 and S ≤ N;
• The remaining marks will be for test cases where N ≤ 5000 and S ≤ N.

Output

Output the minimum possible value of D.

Sample Input 1

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

Sample Output 1

2

Explanation for Sample Input 1

The layout of the cities and roads is like this:

Esdese's army only consists of 1 soldier, and placing that solider at either city 1 or city 2 will result in every city being at most 2 roads away.

Sample Input 2

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

Sample Output 2

2