Bytownの道路網は $n$ 個の交差点と $n-1$ 本の双方向の道路からなり、各道路は直接2つの交差点を結んでいます。また、任意の2つの交差点間は相互に到達可能です。交通を改善するため、市長のByteasarは地下鉄システムの建設を計画しています。具体的には、いくつかの交差点に地下鉄駅を設置し、道路の一部に線路を敷設します。地下鉄ネットワークは連結である必要があります。つまり、列車は任意の2つの地下鉄駅間を、途中で他の地下鉄駅を経由しながら通行できなければなりません。

トンネルの掘削コストは高いですが、終着駅（トンネルが1本しか接続されていない駅）の建設コストはさらに高くなります。これは、これらの駅には列車の停車や保守のための追加のインフラが必要になるためです。財政的な制約により、終着駅の数は最大で $k$ 個までです。一方で、合理的な地下鉄ネットワークには少なくとも2つのそのような駅が必要です。

乗客の「イライラ指数」とは、自宅から出発して最寄りの地下鉄駅まで歩くために通らなければならない最小の道路数と定義されます。市長は、すべての乗客のイライラ指数の最大値を最小化するような地下鉄ネットワークを設計するよう求めています。各交差点には何人かの乗客が住んでいると仮定します。

入力

1行目には、2つの整数 $n$ と $k$ ($n \ge 3, 2 \le k \le n$) がスペース区切りで与えられます。これらはそれぞれ交差点の数と終着駅の最大数を表します。交差点には $1$ から $n$ までの番号が付けられています。

続く $n-1$ 行の各行には、2つの整数 $a$ 和 $b$ ($1 \le a, b \le n, a \neq b$) がスペース区切りで与えられ、交差点 $a$ と $b$ が直接道路で結ばれていることを表します。

出力

1行目に、乗客のイライラ指数の最大値の最小値 $r$ と、その設計における終着駅の数 $s$ ($2 \le s \le k$) をスペース区切りで出力してください。 2行目に、終着駅として設定する交差点の番号を、$1$ から $n$ の範囲で $s$ 個の異なる整数として出力してください。

すべてのネットワーク設計の中で、$r$ が最小となる設計を優先してください。$r$ が同じ場合は、$s$ を最小化することを次善の目標とします。$r$ が最小かつ $s$ が最小となる設計が複数存在する場合は、そのうちのいずれかを出力すればよいです。

入出力例

入力 1

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

出力 1

1 2
8 1

注記

道路網は図の通りです。最適な地下鉄ネットワーク設計には2つの終着駅（交差点1と8）があります。これに対応する乗客のイライラ指数の最大値は1です。$r=1$ かつ $s=2$ を満たす他の最適な地下鉄ネットワーク設計も存在することに注意してください。また、$r=1$ かつ $s=3$ のネットワークも存在しますが、それらは最適ではありません。

サンプルテスト

• 1ocen: $n = 30, k = 29$、交差点 $2, \dots, n$ はすべて交差点 $1$ と接続されている。
• 2ocen: $n = 5000, k = 4000$、交差点 $1, 2, \dots, 2000$ が順に接続されてパスを形成し、交差点 $2001, \dots, 3500$ はすべて交差点 $1$ と接続され、交差点 $3501, \dots, 5000$ はすべて交差点 $2000$ と接続されている。
• 3ocen: $n = 2^{20} - 1, k = 1509$、交差点は完全二分木を構成している。

小課題

テストセットは以下の小課題で構成されています。各小課題には複数のテストケースが含まれる場合があります。 プログラムが1行目のみ正しく出力した場合、そのテストケースの50%のスコアを獲得できます。プログラムは正常に終了し、時間制限およびメモリ制限を超えてはならないことに注意してください。各小課題の時間制限はSIO上で公開されています。