e-olymp
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