Mini March Coding Challenge 2014
Esdeath is excited — she has information that Tatsumi will be appearing today in one of cities, conveniently labeled from to . The Prime Minister (Esdeath's boss) does not care much for the citizens, so there are only 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 soldiers, and she would like to station the soldiers at of the cities such that no matter which city Tatsumi appears in, the minimum distance from any soldier to Tatsumi will be no greater than roads. As one of Esdeath's pets, you'll be rewarded if you can help her find the minimum value of — so do so, and quickly!
The first line of input has 2 integers, and (), the number of cities and the number of soldiers in Esdeath's army, respectively. Each of the next lines contain two integers and , representing a bidirectional road between cities and .
The following additional constraints will apply.
- At least 15% of the marks will be for test cases where and ;
- At least 30% of the marks will be for test cases where and ;
- At least 50% of the marks will be for test cases where and ;
- The remaining marks will be for test cases where and .
Output the minimum possible value of .
Sample Input 1
6 1 1 2 2 4 2 5 2 6 1 3
Sample Output 1
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