Cow barns
In the village of Maksoyaroslavets, cows graze on clearings that are interconnected by paths, with each clearing hosting at least one cow. For any two clearings, there is exactly one unique route to travel between them. These paths are bidirectional and all have the same length.
The chief farmer of the village plans to construct k barns on these clearings for the cows. Each cow will return to the barn closest to its clearing in the evening (if there are multiple barns at the same distance, the cow can choose any of them). The goal is to position the barns such that the longest distance any cow has to travel to reach a barn is minimized.
Input
The first line of the input contains two integers n and k (2 ≤ n ≤ 50000, 1 ≤ k ≤ n), representing the number of clearings and the number of barns to be built, respectively. The following n-1 lines describe the paths. Each path is represented by a pair of positive integers (a, b), indicating that clearings a and b are connected by that path. Clearings are numbered starting from one.
Output
On the first line of the output, print l - the maximum number of paths a cow needs to traverse to reach a barn. On the second line, print k distinct integers - the numbers of the clearings where the barns should be constructed. If there are multiple optimal solutions, any one of them can be provided.