Задачі
Корівники
Корівники
У селі Максоярославці корови за звичай пасуться на галявинах, з'єднаних доріжками, на кожній галявині пасеться хоча б одна корова. При цьому для кожної пари галявин є рівно один спосіб пройти від однієї галявини до іншої. По кожній доріжці можна рухатись в обох напрямках. Вважається, що усі доріжки мають однакову довжину.
Головний фермер села хоче побудувтаи на галявинах \textbf{k} корівників для своїх корів. Зрозуміло, що кожна корова увечері будет повертатись саме у той корівник, який найближче до її галявини (якщо відстань до корівників однакові, то у довільний з них). Тому виикає задача визначення такого розміщення корівників, при якому найбільша з відстаней, які проходять корови, була б мінімальною.
\InputFile
У першому рядку вхідного файлу містяться два числа \textbf{n} та \textbf{k} (\textbf{2} ≤ \textbf{n} ≤ \textbf{50000}, \textbf{1} ≤ \textbf{k} ≤ \textbf{n}) - кількість галявин та заплановане число корівників, відповідно. Наступні \textbf{n-1} рядків містять описи доріжок. Кожна доріжк задається парою цілих додатних чисел (\textbf{a}, \textbf{b}), де \textbf{a} та \textbf{b} - номера галявин, які з'єднує дана доріжка. Галявини нумеруються з одиниці.
\OutputFile
У першому рядку вихідного файлу виведіть \textbf{l} - максимальну кількість доріжок, по яким прийдеться пройти корові, щоб потрапити у корівник. У другому рядку виведіть \textbf{k} різних цілих чисел - номери галявин, на яки слід побудувати корівники. Якщо оптимальних розв'язків декілька, дозволяється вивести довільний з них.
Вхідні дані #1
7 2 5 4 4 3 1 3 2 3 4 6 6 7
Вихідні дані #1
2 1 4