Задачи
Вершинное покрытие
Вершинное покрытие
Имеется невзвешенное неориентированное дерево. Найдите такое наименьшее подмножество вершин, что для любого ребра хотя бы один из его концов принадлежит этому множеству.
Входные данные
Первая строка содержит количество вершин 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