Məsələlər
Пастбищa
Пастбищa
Фермер Джон решил снабдить каждую из его коров сотовым телефоном. Для этого ему требуется установить сотовые станции на его \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{100000}) пастбищах (последовательно пронумерованных от \textbf{1} до \textbf{N}).
Ровно \textbf{N-1} пара пастбищ являются соседними, и для любых двух пастбиищ \textbf{A} и \textbf{B} (\textbf{1} ≤ \textbf{A} ≤ \textbf{N}; \textbf{1} ≤ \textbf{B} ≤ \textbf{N}; \textbf{A} ≠ \textbf{B}), имеется последовательность соседних пастбищ таких, что \textbf{A} - первое пастбище этой последовательности, а \textbf{B} - последнее. Сотовые станции размещаются только в пастбищах. И они должны иметь достаточный радиус действия, чтобы обеспечить связью это пастбище и все соседние.
Помогите фермеру Джону определить минимальное количество станций, которое он должен установить, чтобы обслуживать все пастбища.
\InputFile
В первой строке входного файла находится одно целое число \textbf{N}. Далее следуют \textbf{N-1} строк, каждая из которых содержит два разделенных пробелами числа - очередная пара соседних пастбищ.
\OutputFile
Выведите в выходной файл одно число - минимальное достаточное количество станций.
Giriş verilənləri #1
5 1 3 5 2 4 3 3 5
Çıxış verilənləri #1
2