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