Заражение

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

Вместе они наблюдают за $n$ фермами, пронумерованных от $1$ до $n$. Фермы соединены $n-1$ дорогой, так что к любой ферме можно добраться от фермы $1$ по некоторой последовательности дорог.

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

• На одной ферме событие "суперразброс" приводит к удвоению количества коров с COWVID-19;

• Одна корова с COWVID-19 движется по дороге от одной фермы к соседней.

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

Входные данные

Первая строка содержит единственное целое число $n(1\le n\le 10^5)$. Каждая из следующих $n-1$ строк содержит два целых числа $a$ и $b$, описывающих дорогу между фермами $a$ и $b$. Оба значения $a$ и $b$ находятся в диапазоне $\mathrm{1...}n$.

Выходные данные

Выведите минимальное количество дней до того, как вспышка болезни достигнет каждой фермы.

Примеры

Одна из возможных последовательностей событий, соответствующая этому примеру, следующая: количество больных коров на ферме $1$ удваивается, затем снова удваивается, так что через два дня на ферме $1$ оказывается $4$. В каждый из следующих $3$ дней больная корова идет с фермы $1$ на каждую из ферм $2,3$ и $4$ соответственно. Через $5$ дней на каждой ферме будет как минимум $1$ больная корова.