The town administration has decided to embellish the landscape by building
new parks. To make the parks not only look good, but also be useful, they
need to carefully choose which neighbourhoods to build the parks in so that
the kids from the other neighbourhoods have at least one park near them.
The town consists of \(n\) neighbourhoods connected by \(n - 1\) roads of a certain
length. There is a unique path connecting each neighbourhood to any other
neighbourhood. In other words, the neighbourhoods and roads form a tree.
Exactly \(k\) parks should be built in different neighbourhoods so that the other
neighbourhoods have their nearest park as close to them as possible. To be
more precise, the administration wants to minimize the maximum distance from a neighbourhood to its
closest park.
Help the town administration and determine which neighbourhoods should have a park built in them and
determine the maximum distance from a neighbourhood to its closest park.

Subtask 1 (10 points): \(1 \le n \le 20\)

Subtask 2 (10 points): \(k = 1\)

Subtask 3 (30 points): \(a_{i} = i\), \(b_{i} = i + 1\) for all \(1 \le i \le n - 1\)

Subtask 4 (60 points): No additional constraints.

The first line contains two positive integers \(n\) and \(k\) (\(1 \le k \le n \le 200\,000\)), the number of neighbourhoods
and the number of parks, respectively.
The \(i-th\) of the next \(n - 1\) lines contains positive integers \(a@@RISE_MATH_BLOCK_0@@i\) and \(w@@RISE_MATH_BLOCK_1@@i\), b\(i \le n\), \(1 \le w\)\(i \le 10^{9}\)),
which denotes that the neighbourhoods labeled \(a_{i}\) and \(b_{i}\) are connected by a road of length \(w_{i}\).

In the first line print the least possible maximum distance from the problem statement.
In the second line print \(k\) positive integers, the labels of the neighbourhoods which will have a park built
in them. If there is more than one solution, output any one.

생성자가 기록되지 않았습니다.

출처 COCI 2021/2022 Contest 4