Warehouse Delivery Optimization

Given a tree of warehouses connected by roads, choose k warehouses to be designated as main hubs such that, after adding direct routes between the hubs, the maximum delivery distance from any warehouse to its nearest main hub is minimized.

Let \(D\) be the diameter of the tree (i.e. the maximum distance between any pair of warehouses). The answer is defined as follows:

• If \(k \ge n\), then the answer is 0.
• If \(k = 1\), then the answer is \(\lceil \frac{D}{2} \rceil\).
• For \(k \ge 2\), the answer is \(\left\lfloor \frac{D+1-(k-2)}{2} \right\rfloor\).

Your task is to compute the minimum possible maximum delivery distance from any warehouse to its nearest hub using the optimal hub placement.

inputFormat

The input is read from standard input (stdin). The first line contains two integers, (n) and (k), separated by a space, where (n) is the number of warehouses and (k) is the number of main hubs to choose. The next (n-1) lines each contain two integers (u) and (v), indicating that there is a road connecting warehouse (u) and warehouse (v).

outputFormat

Output a single integer to standard output (stdout), representing the minimum possible maximum delivery distance from any warehouse to its nearest main hub under an optimal hub placement.## sample

6 2
1 2
1 3
3 4
3 5
5 6

2