Погоня за бабочкой
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ясными летними днями Нюша любит ловить бабочек на свежем воздухе. Сегодня ей попалась хитрая бабочка: она залетела в лабиринт и хотела скрыться в нем от Нюши.

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

Вход в лабиринт расположен в комнате с номером $$$1$$$. Будем называть листом любую комнату лабиринта, которая соединена коридором ровно с одной другой комнатой и не совпадает при этом с корнем. В каждом из листов располагается выход из лабиринта. Бабочка летит от входа по направлению к одному из листов. Она летит с постоянной скоростью и не разворачивается. Все коридоры имеют одинаковую длину, и за одну минуту бабочка пролетает один коридор, перемещаясь в соседнюю комнату.

Для поимки бабочки, Нюша решила позвать несколько своих друзей. Исходно каждый из друзей может расположиться в любой из комнат, содержащих выход. В тот момент, когда бабочка начнет лететь от входа в лабиринт к одному из выходов, каждый из друзей может начать двигаться из своей комнаты по направлению ко входу. Друзья двигаются с такой же скоростью, что и бабочка. Если кто-то из друзей оказался в одной точке (в комнате или в середине одного из коридоров) с бабочкой, то бабочка считается пойманной. Если же бабочка долетит до вершины с выходом, не встретив никого из друзей по пути, она благополучно выпорхнет из лабиринта и улетит на свободу.

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

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

Первая строка входных данных содержит целое число $$$n$$$ — количество комнат в лабиринте ($$$2 \le n \le 200\,000$$$).

В следующих $$$n - 1$$$ строках содержатся описания коридоров, соединяющих комнаты. Каждая из этих строк содержит два целых числа $$$u$$$ и $$$v$$$ — номера комнат, которые соединяет коридор ($$$1 \le u, v \le n$$$; $$$u \neq v$$$). Гарантируется, что структура коридоров представляет собой дерево.

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

Выведите одно целое число — минимальное количество друзей, необходимое для того, чтобы гарантированно поймать бабочку.

Примеры

Входные данные
3
1 2
1 3
Выходные данные
2
Входные данные
4
1 2
2 3
2 4
Выходные данные
1