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

Разом вони спостерігають за колекцією з \(N\) ферм (\(1 \leq N \leq 10^5\)), послідовно пронумерованих \(1 \ldots N\). Ці ферми з'єднані множиною з \(N-1\) доріг так, що будь-яка ферма досяжна від ферми 1 деякою послідовністю доріг.

На жаль, одна корова на фермі 1 має позитивний тест на КОВІД-19. Жодні з інших корів на цій та інших фермах поки не хворі. Однак у зв'язку з високою контагенозністю цієї хвороби ФД очікує точно одну з наступних несприятливих подій кожен наступний день:

(1) На фермі кількість корів з КОВІД-19 подвоюється

(2) Одна корова з КОВІД-19 переміщається дорогою з однієї ферми до сусідньої.

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

Формат вхідних даних

Перший рядок містить одне ціле число \(N\). Кожен з наступних \(N-1\) рядків містить два розділені пропуском числа \(a\) і \(b\), що описують дорогу між фермами \(a\) і \(b\). \(a\) і \(b\) в інтервалі \(1\ldots N\).

Формат вихідних даних

Мінімальна кількість днів, щоб хвороба досягла кожної ферми.

Приклад вхідних даних

4
1 2
1 3
1 4

Приклад вихідних даних

5

Одна з можливих послідовностей подій для цього прикладу така: Кількість хворих корів на фермі 1 подвоїться і потім подвоїться ще раз, Тому через два дні на фермі 1 буде 4 хворих корови. У кожен з наступних 3 днів хвора корова перейде із ферми 1 на ферму 2,3,4. Після 5 днів щонайменше одна хвора корова буде на кожній фермі.

Оцінювання:

• У тестах 1-4 кожна ферма(крім ферми 1) з'єднана безпосередньо з фермою 1.
• У тестах 5-7 кожна з ферм \(2\ldots N\) має не більше двох доріг.
• У тестах 8-15 немає додаткових обмежень.