Mini March Coding Challenge 2014

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 Specification

The first line of input has 2 integers, ~N~ and ~S~ ~(1 \le S \le N \le 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 \le 100~ and ~S = 1~;
• At least 30% of the marks will be for test cases where ~N \le 100~ and ~S \le 10~;
• At least 50% of the marks will be for test cases where ~N \le 250~ and ~S \le N~;
• The remaining marks will be for test cases where ~N \le 5000~ and ~S \le N~.

Output Specification

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 Output 1

The cities and roads are laid out like the following:

Esdeath's army only consists of 1 soldier, and placing that soldier 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

This problem statement is the exclusive and proprietary property of DMOJ. Any unauthorized use or reproduction of this information without the prior written consent of DMOJ is strictly prohibited. (c)2014, DMOJ. All rights reserved.