Cow barns#5298
In the village of Maksoyaroslavets, cows usually graze in clearings, which are interconnected by paths, with at least one cow grazing in each clearing. For every pair of clearings, there is exactly one unique way to go from one to the other using these paths. Each path is bidirectional and all paths are of the same length.
The chief farmer of the village wants to build barns in the clearings for his cows. Each cow, in the evening, will return to the barn closest to its clearing (if there are several barns at the same distance, a cow can choose any of them). The goal is to locate the barns so that the maximum number of paths a cow needs to traverse to reach a barn is minimized.
The first line contains two integers and (2 \leq n \leq 50000, 1 \leq k \leq n) — the number of clearings and the number of barns to build, respectively. The following n-1 lines each contain two positive integers and , indicating that clearings and are connected by a path. The clearings are numbered from .
On the first line, print — the maximum number of paths a cow needs to traverse to reach a barn. On the second line, print distinct integers — the numbers of the clearings where the barns should be built. If there are multiple optimal solutions, you may print any of them.
Example 1