Зараження#10367

Зараження

1 секунда

128 мегабайтів

Складна

Фермер Джон та його колеги працюють без зупинки, намагаючись стримати поширення небезпечної хвороби великої рогатої худоби COWVID-19 на своїх фермах.

Усього під наглядом знаходиться $n$ ферм, пронумерованих від $1$ до $n$ . Ферми з'єднані $n - 1$ n-1 дорогами, причому від ферми $1$ можна дістатися до будь-якої іншої по певній послідовності доріг.

На жаль, корова на фермі $1$ щойно отримала позитивний результат на COWVID-19. Поки що жодна інша корова — ні на цій, ні на інших фермах — не заражена. Однак, враховуючи надзвичайно високу заразність хвороби, фермер Джон розуміє, що кожного наступного дня може відбутися одна з двох подій:

на одній із ферм відбувається суперпоширення, внаслідок чого кількість заражених корів на цій фермі подвоюється;
одна заражена корова переходить по дорозі з однієї ферми на сусідню.

Фермер Джон стурбований тим, наскільки швидко може поширитися спалах хвороби. Допоможіть йому визначити мінімальну кількість днів, необхідних для того, щоб на кожній фермі з'явилася хоча б одна заражена корова.

Вхідні дані

Перша строка містить одне ціле число $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5). Кожна з наступних $n - 1$ n - 1 строк містить два цілих числа $a$ і $b$ , які позначають дорогу між фермами $a$ і $b (1 \leq a, b \leq n)$ b~(1 \le a, b \le n).

Вихідні дані

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

Приклади

Одна з можливих послідовностей подій, що відповідає прикладу, виглядає так:

спочатку кількість заражених корів на фермі $1$ двічі подвоюється, і через $2$ дні їх стає $4$ . Потім протягом наступних $3$ днів по одній зараженій корові переходить з ферми $1$ на ферми $2$ , $3$ та $4$ відповідно. Таким чином, через $5$ днів на кожній фермі буде принаймні одна заражена корова.

Приклад 1