Sieć ulic w Bytown składa się z $n$ skrzyżowań i $n-1$ dwukierunkowych ulic, z których każda łączy bezpośrednio parę skrzyżowań, przy czym każde skrzyżowanie jest osiągalne z każdego innego. Aby usprawnić ruch, burmistrz Byteasar chce zbudować system metra. W szczególności chce on wyznaczyć niektóre skrzyżowania jako stacje metra i położyć tory wzdłuż części ulic. Sieć metra powinna być spójna, co oznacza, że pociągi muszą mieć możliwość przejazdu między dowolnymi dwiema stacjami metra, być może przejeżdżając przez inne stacje po drodze.

Koszt budowy tuneli jest wysoki, ale koszt budowy stacji końcowych (tj. stacji, do których prowadzi tylko jeden tunel) jest jeszcze wyższy, ponieważ wymagają one dodatkowej infrastruktury do parkowania i serwisowania pociągów. Ze względów finansowych liczba stacji końcowych może wynosić co najwyżej $k$. Z drugiej strony, rozsądna sieć metra wymaga co najmniej dwóch takich stacji.

„Wskaźnik irytacji” pasażera to minimalna liczba ulic, które musi on pokonać, idąc pieszo z domu do najbliższej stacji metra. Burmistrz wymaga zaprojektowania sieci metra tak, aby zminimalizować maksymalny wskaźnik irytacji wszystkich pasażerów. Zakładamy, że na każdym skrzyżowaniu mieszkają pasażerowie.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $k$ ($n \ge 3, 2 \le k \le n$), oddzielone spacją, oznaczające odpowiednio liczbę skrzyżowań oraz maksymalną liczbę stacji końcowych. Skrzyżowania są ponumerowane od $1$ do $n$.

Kolejne $n-1$ linii zawiera po dwie liczby całkowite $a$ oraz $b$ ($1 \le a, b \le n, a \neq b$), oddzielone spacją, oznaczające, że skrzyżowania $a$ i $b$ są połączone bezpośrednio ulicą.

Wyjście

W pierwszej linii należy wypisać dwie liczby całkowite $r$ oraz $s$, oddzielone spacją, oznaczające odpowiednio minimalną wartość maksymalnego wskaźnika irytacji oraz liczbę stacji końcowych w tym projekcie (spełniającą $2 \le s \le k$). W drugiej linii należy wypisać $s$ różnych liczb całkowitych z zakresu od $1$ do $n$, odpowiadających numerom skrzyżowań, na których znajdują się stacje końcowe.

Spośród wszystkich projektów sieci należy w pierwszej kolejności wybrać ten, dla którego $r$ jest najmniejsze. W przypadku remisu, drugorzędnym celem jest zminimalizowanie $s$. Jeśli istnieje wiele projektów spełniających warunki minimalnego $r$ oraz minimalnego $s$, można wypisać dowolny z nich.

Przykład

Przykład 1

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

Wyjście 1

1 2
8 1

Uwagi

Sieć ulic przedstawiono na rysunku. Optymalny projekt sieci metra ma dwie stacje końcowe (zlokalizowane na skrzyżowaniach 1 i 8). Odpowiadający mu maksymalny wskaźnik irytacji pasażerów wynosi 1. Należy zauważyć, że istnieją inne optymalne projekty sieci metra spełniające $r=1$ oraz $s=2$. Istnieją również sieci z $r=1$ oraz $s=3$, ale nie są one optymalne.

Testy przykładowe

• 1ocen: $n = 30, k = 29$, skrzyżowania $2, \dots, n$ są połączone ze skrzyżowaniem $1$.
• 2ocen: $n = 5000, k = 4000$, skrzyżowania $1, 2, \dots, 2000$ tworzą ścieżkę, skrzyżowania $2001, \dots, 3500$ są połączone ze skrzyżowaniem $1$, a skrzyżowania $3501, \dots, 5000$ są połączone ze skrzyżowaniem $2000$.
• 3ocen: $n = 2^{20} - 1, k = 1509$, skrzyżowania tworzą pełne drzewo binarne.

Podzadania

Zestaw testów składa się z następujących podzadań. Każde podzadanie może zawierać wiele punktów testowych. Jeśli program wypisze poprawnie tylko pierwszą linię, otrzyma 50% punktów za dany punkt testowy. Należy pamiętać, że program musi zakończyć się poprawnie i nie przekroczyć limitów czasu ani pamięci. Limity czasu dla poszczególnych podzadań są opublikowane na SIO.