Ясными летними днями Нюша любит ловить бабочек на свежем воздухе. Сегодня ей попалась хитрая бабочка: она залетела в лабиринт и хотела скрыться в нем от Нюши.
Лабиринт состоит из $$$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