eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Боб в стране чудес

Боб в стране чудес

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Цепь, как известно, состоит из связанных звеньев. Обычно все звенья имеют одинаковую форму и размер. Боб - ученик кузнеца, и он делает свою первую иридиевую цепочку. Он следует традиционной формуле создания цепей. Она гласит:

  • Если цепочки еще нет, сделайте звено, и оно станет частью вашей цепочки..

  • Если уже имеется кусок цепи, сделайте еще одно звено и соедините его с другим звеном в цепи.

Боб сделал первое звено. Затем, каждый раз, когда он создавал новое звено, он соединял его с каким-нибудь другим звеном цепи, в точности так, как ему говорит формула.

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

Для Боба было очевидно, что его работа еще не закончена, и он решил назвать созданный им объект незавершенной цепочкой. Поразмыслив еще немного, Боб пришел к выводу, что он должен разорвать некоторые звенья и аккуратно соединить их с остальной частью незавершенной цепи, чтобы получить прямую цепь, которую он намеревается сделать. В прямой цепи каждое звено соединено не более чем с двумя другими звеньями. Прямая цепь не может быть разделена на несколько частей без разрыва звена.

Будучи теперь более осторожным, Боб будет продвигаться вперед простыми шагами. На одном шаге он выберет звено A, связанное с другим звеном B, в незавершенной цепочке. Затем он сломает A, отсоединит его от B и повторно подсоединит A к какому-либо другому звену, например C, в незавершенной цепочке. Если имеются еще звенья, кроме B, изначально подключенные к A, то Боб будет поддерживать их подключенными к A на протяжении всего шага.

Какое минимальное количество шагов должен выполнить Боб, чтобы получить прямую цепочку?

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

В первой строке записано одно целое число n~(1 \le n \le 3 \cdot 10^5) — количество звеньев в незавершенной цепочке. Звенья помечены как 1, 2, ..., п. В каждой из следующих n - 1 строк заданы два целых числа, обозначающих метки двух связанных звеньев незавершенной цепочки. Подключения перечислены в произвольном порядке. Незавершенная цепочка гарантированно образует только одно целое.

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

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

Пример

Входные данные #1
5
4 3
1 2
4 5
3 2
Выходные данные #1
0
Входные данные #2
6
1 3
3 2
3 4
4 5
4 6
Выходные данные #2
2
Входные данные #3
7
1 2
2 3
3 4
4 5
3 6
6 7
Выходные данные #3
1
Источник 2019 ACM Central Europe (CERC), Прага, Ноябрь 29 - Декабрь 1, Задача C