Олімпійські товари#11754

Олімпійські товари

1 секунда

128 мегабайтів

Легка

На ринок щойно вийшов новий ритейлер YAOGS (Yet Another Olympic Goodies Seller), який продає надзвичайно дорогі товари з олімпійською тематикою. Щоб підвищити впізнаваність серед публіки, компанія вирішила організувати конкурс, роздаючи частину цих товарів. Переможцем стане той, хто першим правильно відповість на запитання: "Скільки кілець у логотипі Олімпійських ігор?". Він зможе отримати до $p$ дуже дорогих, але рівноцінних предметів.

Щоб додати інтриги (і заощадити), YAOGS запроваджує додаткову умову.

Доступні $p$ предметів розміщуються вздовж деяких, але, можливо, не всіх алей штаб-квартири YAOGS. Кожна алея може містити $0$ , $1$ або більше предметів. З невідомих причин ці алеї утворюють зв'язний, неорієнтований, ациклічний граф (тобто дерево) з $n$ вершинами, пронумерованими від $0$ до $n - 1$ n - 1.

Переможець знає $n$ , але не знає ані структури дерева, ані розташування предметів. Після того, як предмети розставлені, його завдання — вибрати початкову вершину $m$ та кінцеву вершину $n$ . Потім він може зібрати всі предмети, які знаходяться на (єдиному) шляху від $m$ до $n$ у дереві.

YAOGS вирішує розмістити предмети так, щоб мінімізувати максимальну кількість предметів, які можна зібрати. Припускаючи, що ця умова виконана, яка максимальна кількість предметів може бути зібрана переможцем?

Вхідні дані

Перший рядок містить два цілих числа $n$ і $p (1 \leq n, p \leq 1 0^{5})$ p~(1 \leq n, p \leq 10^5). Далі йдуть $n - 1$ n - 1 рядків, кожен з яких містить два цілих числа $a_{k}$ a_k і $b_{k} (0 \leq a_{k}, b_{k} \leq n - 1)$ b_k~(0 \leq a_k, b_k \leq n - 1), які означають, що між вершинами $a_{k}$ a_k і $b_{k}$ b_k дерева існує ребро. Задана множина ребер описує коректну структуру дерева.

Вихідні дані

Виведіть одне ціле число: максимальну кількість предметів, яку може зібрати переможець.

Приклади

Для дерева з прикладу, зображеного нижче, оптимальне розміщення предметів за допомогою YAOGS гарантує, що переможець не зможе зібрати більше ніж чотири предмети.

На рисунках нижче показано два можливих варіанти розміщення предметів, які забезпечують цю оптимальність. У першому випадку чотири предмети можна зібрати, обравши, наприклад, вершини $1$ та $3$ . У другому випадку чотири предмети можна зібрати, обравши, наприклад, вершини $0$ та $4$ .

Приклад 1