Minimizing Maximum Subtree Diameter

Farmer John has a tree of V nodes (numbered 1…V) connected by V-1 bidirectional roads (each of length 1) so that there is a unique simple path between any two nodes. The cows compute the diameter of the tree (the maximum distance between any two nodes). In order to have a shorter exercise path, Farmer John can choose to block exactly S roads (with 1 ≤ S ≤ V-1), thereby partitioning the tree into S+1 connected subtrees. His goal is to choose a set of S roads to block so that the maximum diameter among all the resulting subtrees is minimized.

Task: Given the tree and the integer S, determine the minimum possible value of the largest diameter among the S+1 subtrees obtained by optimally removing S edges.

Note: The diameter of a tree is defined as the longest distance (in terms of the number of edges) between any two nodes in that tree. If an isolated node is obtained, its diameter is 0.

Hint: One can use a decision procedure with binary search on the candidate maximum diameter D. For a candidate D, observe that if a connected subtree has diameter at most D, then it has a center such that every node in this subtree is within distance r of the center, where r = ceil(D/2). The problem reduces to covering the tree with as few "centers" (i.e. balls of radius r) as possible. If the number of centers needed is at most S+1, then D is feasible.

inputFormat

The first line contains two integers V and S (2 ≤ V ≤ 10⁵, 1 ≤ S ≤ V-1), representing the number of nodes and the number of roads to block, respectively.

Each of the following V-1 lines contains two integers A_i and B_i (1 ≤ A_i, B_i ≤ V and A_i ≠ B_i), indicating there is a road connecting vertices A_i and B_i.

outputFormat

Output a single integer --- the minimum possible value of the maximum diameter among the S+1 subtrees obtained by optimally blocking S roads.

sample

4 1
1 2
2 3
3 4

1