Корівники#5298
У селі Максоярославці корови зазвичай пасуться на галявинах, які з'єднані стежками, причому на кожній галявині пасеться хоча б одна корова. Для кожної пари галявин існує рівно один унікальний шлях від однієї до іншої цими стежками. Кожна стежка є двосторонньою, і всі стежки мають однакову довжину.
Головний фермер села хоче побудувати корівників на галявинах для своїх корів. Кожна корова ввечері буде повертатися до корівника, який знаходиться найближче до її галявини (якщо відстань до кількох корівників однакова, вона може вибрати будь-який з них). Потрібно розмістити корівники так, щоб максимальна кількість стежок, яку доведеться пройти корові до корівника, була мінімальною.
У першому рядку містяться два цілих числа і (2 \leq n \leq 50000, 1 \leq k \leq n) — кількість галявин і кількість корівників відповідно. Наступні n-1 рядків містять по два додатних цілих числа і , які означають, що галявини і з’єднані стежкою. Галявини пронумеровані від .
У першому рядку виведіть — максимальну кількість стежок, яку доведеться пройти корові, щоб потрапити в корівник. У другому рядку виведіть різних цілих чисел — номера галявин, на яких слід побудувати корівники. Якщо оптимальних рішень кілька, дозволяється вивести будь-яке з них.
Приклад 1