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