Mini March Coding Challenge 2014

Esdeath

Esdeath is excited — she has information that Tatsumi will be appearing today in one of N cities, conveniently labeled from 1 to N. The Prime Minister (Esdeath's boss) does not care much for the citizens, so there are only N−1 bidirectional roads connecting the cities, and all cities are connected to every other city by just 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 ui and vi, representing a bidirectional road between cities ui and vi.

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 ≤ 10;
  • 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 cities and roads are laid out like the following:

Esdeath'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

All Submissions
Best Solutions


Point Value: 20 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: Mar 19, 2014
Author: FatalEagle

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3