Пасовища#1766
Фермер Джон вирішив дати кожній зі своїх корів мобільний телефон, сподіваючись заохотити їх до соціальної взаємодії. Однак для цього йому потрібно встановити вежі мобільного зв'язку на своїх (1 \leq N \leq 100\,000) пасовищах (зручно пронумерованих від до ), щоб усі могли спілкуватися.
Рівно N - 1 пар пасовищ є сусідніми, і для будь-яких двох пасовищ і (1 \leq A \leq N; 1 \leq B \leq N; A \neq B) існує послідовність сусідніх пасовищ, така що є першим у цій послідовності, а — останнім. Вежі мобільного зв'язку можна встановлювати лише на пасовищах, і кожна вежа має достатній радіус дії, щоб обслуговувати пасовище, на якому вона встановлена, а також усі сусідні пасовища.
Допоможіть фермеру Джону визначити мінімальну кількість веж, які потрібно встановити, щоб забезпечити мобільним зв'язком усі пасовища.
Перший рядок містить одне ціле число . Кожен з наступних N - 1 рядків містить по два цілих числа, що описують пару сусідніх пасовищ.
Виведіть одне ціле число — мінімальну кількість необхідних веж.
Приклад 1