e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

Пятёрка за неделю 22

Пастбищa

Фермер Джон решил снабдить каждую из его коров сотовым телефоном. Для этого ему требуется установить сотовые станции на его N (1N100000) пастбищах (последовательно пронумерованных от 1 до N).

Ровно N-1 пара пастбищ являются соседними, и для любых двух пастбиищ A и B (1AN; 1BN; AB), имеется последовательность соседних пастбищ таких, что A - первое пастбище этой последовательности, а B - последнее. Сотовые станции размещаются только в пастбищах. И они должны иметь достаточный радиус действия, чтобы обеспечить связью это пастбище и все соседние.

Помогите фермеру Джону определить минимальное количество станций, которое он должен установить, чтобы обслуживать все пастбища.

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

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

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

Выведите в выходной файл одно число - минимальное достаточное количество станций.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
5
1 3
5 2
4 3
3 5
Çıxış verilənləri #1
2