### 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 `u _{i}` and

`v`, representing a bidirectional road between cities

_{i}`u`and

_{i}`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`≤ 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

## Comments (Search)

Alexon Mar 20, 2014 - 10:12:30 pm UTC The author has supplied 10 new test cases, which have been added