Республиканская олимпиада по информатике 2020 года за 11 класс | Казахстанские олимпиады

Maximum matching

Дано дерево из $n$ $(2 \leq n \leq 10^5)$ вершин и положительное число $k (1 \leq k \leq n/2)$. В этом дереве надо выбрать $k$ пар вершин, так чтобы каждая вершина встречалась максимум в одной паре, и суммарное расстояние было максимальным. То есть надо выбрать пары ($x_i$, $y_i$) $(1 \leq i \leq k)$ так, чтобы $\sum^k_{i=1} dis(x_i, y_i)$ — было максимальным и множество вершин $x_1, x_2, ..., x_k, y_1, y_2, ..., y_k$ были различными. $dis(u, v)$ расстояние между вершинами $u$ и $v$ в дереве.

Формат входного файла

В первой строке содержится два целых числа $n$ и $k$. В следующих $n − 1$ строках заданы рёбра дерева в формате $a_i, b_i (1 \leq a_i, b_i \leq n)$. Гарантируется, что заданный граф является деревом

Формат выходного файла

Выведите $k$ строк, в каждой строке две вершины $x_i, y_i (1 \leq i \leq k)$. Если существует несколько правильных ответов, выведите любой из них.

Примеры

Вход

3 1
1 2
1 3

Выход

3 2

Вход

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

Выход

7 6
3 5
4 1