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