Фермер Джон и его друзья фермеры борются с распространением COVID-19 среди своих коров.
Вместе они наблюдают за коллекцией из \(N\) ферм (\(1 \leq N \leq 10^5\)),
последовательно пронумерованных \(1 \ldots N\). Эти фермы соединены множеством из
\(N-1\) дорог так, что любая ферма достижима от фермы 1 некоторой последовательностью
дорог.
К несчастью, одна корова на ферме 1 дала положительный тест на КОВИД-19.
Никакие из других коров на этой и других фермах пока не больны.
Однако, в связи с высокой контагенозностью этой болезни, ФД ожидает
точно одно из следующих неблагоприятных событий каждый последующий день:
(1) На ферме количество коров с КОВИД-19 удваивается
(2) Одна корова с КОВИД-19 перемещается по дороге с одной фермы
на соседнюю ферму.
ФД волнуется как быстро распространится болезнь. Помогите ему определить
минимально возможное количество дней, чтобы на каждой ферме была
хоть одна заболевшая корова.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит одно целое число \(N\). Каждая из следующих \(N-1\) строк
содержит два разделённых пробелом числа \(a\) и \(b\), описывающих дорогу между
фермами \(a\) и \(b\). \(a\) и \(b\) в интервале \(1\ldots N\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Минимальное количество дней, чтобы болезнь достигла каждой фермы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
1 3
1 4
|
5
|