Defense

Interview

Time limit2sMemory limit1024 MB

Summary

Given a tree of k portals, pick n of them so the smallest pairwise distance is as large as possible, then print that distance.

Level: Medium6 of 10
Topics: Binary search, Tree, Dynamic programming
Solved: No attempts yet

Statement

Recently, the army of the Dark Elves led by Malekith invaded Midgard. Their goal was to destroy the universe at the moment the worlds converge, using the Aether. Thor and his friend Jane Foster barely managed to repel the attack. In five thousand years the worlds will converge again, and Odin decided to prevent another attack. He ordered his chief engineer to create one more world, an intermediate one. Anyone who wants to travel from one world to another must first pass through this intermediate world.

The universe consists of $n$ worlds (not counting the intermediate one). The intermediate world has $k$ portals. These $k$ portals are connected by $k - 1$ roads, and every portal can reach every other portal. Choose $n$ portals so that the shortest distance between two chosen portals is as large as possible. Print this distance.

Input

The first line contains two integers $k$ and $n$ ( $2 \le n \le k \le 250$ ), the number of portals and the number of worlds. Each of the next $k - 1$ lines contains $a$ , $b$ ( $1 \le a, b \le k$ ), the numbers of two portals connected by a road.

Output

Print the answer to the problem on a single line.

Examples2

Example 1
Input
```
5 3
1 5
2 4
5 4
1 3
```
Expected output
```
2
```
Example 2
Input
```
5 2
2 1
3 5
2 5
4 3
```
Expected output
```
4
```