Задачи
Вершинное покрытие
Вершинное покрытие
Имеется невзвешенное неориентированное дерево. Найдите такое наименьшее подмножество вершин, что для любого ребра хотя бы один из его концов принадлежит этому множеству.
\includegraphics{https://static.e-olymp.com/content/b9/b91b096d8150f877ba7b7772586cd6954df650a2.gif}
\InputFile
Первая строка содержит количество вершин $n~(0 < n \le 10^5)$ в дереве. Следующие $n - 1$ строк задают $n - 1$ ребро дерева. Каждая строка содержит пару $(u, v)$ означающую наличие ребра между вершинами $u$ и $v~(1 \le u, v \le n)$.
\OutputFile
Выведите количество вершин в искомом подмножестве.
Входные данные #1
6 1 2 1 3 2 4 2 5 1 6
Выходные данные #1
2