eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Вершинне покриття

Вершинне покриття

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Дано незважене неорієнтоване дерево. Знайдіть таку найменшу підмножину вершин, що для будь-якого ребра хоча б один з його кінців належить цій множині.

Вхідні дані

Перший рядок містить кількість вершин n~(0 < n \le 10^5) в дереві. Далі n - 1 рядків задають n - 1 ребро дерева. Кожен рядок містить пару (u, v), що означає нявність ребра між вершинами u і v~(1 \le u, v \le n).

Вихідні дані

Виведіть кількість вершин в шуканій підмножині.

Приклад

Вхідні дані #1
6
1 2
1 3
2 4
2 5
1 6
Вихідні дані #1
2