F. Зубликанцы и мумократы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Берляндии наступила пора выборов. Фаворитами конечно являются партии зубликанцев и мумократов. Предвыборные кампании обеих партий включают в себя многочисленные митинги на n главных площадях столицы Берляндии. На каждой из n площадей конечно может митинговать только одна партия, иначе это может привести к беспорядкам. С другой стороны обе партии подали заявки на проведение огромного количества митингов так, что на всех площадях обязательно пройдут митинги. Теперь руководству столицы предстоит распределить площади между двумя партиями.

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

Мэр столицы поручил распределить все площади между партиями таким образом, чтобы в тупиковых площадях было одинаковое количество митингов первой и второй партии. Гарантируется, что количество тупиковых площадей города чётно.

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

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

В первой строке входных данных находится целое число n (2 ≤ n ≤ 5000) — количество площадей в столице Берляндии.

В следующих n - 1 строках находятся пары чисел x, y (1 ≤ x, y ≤ n, x ≠ y) — номера площадей, соединенных дорогой. Все площади нумеруются целыми числами от 1 до n. Гарантируется, что количество тупиковых площадей города — четно.

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

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

Примеры
Входные данные
8
1 4
2 4
3 4
6 5
7 5
8 5
4 5
Выходные данные
1
Входные данные
5
1 2
1 3
1 4
1 5
Выходные данные
2