Problems
Vertex Cover
Vertex Cover
You are given an unweighted, undirected tree. Write a program to find a vertex set of minimum size in this tree such that each edge has as least one of its end-points in that set.
\includegraphics{https://static.e-olymp.com/content/b9/b91b096d8150f877ba7b7772586cd6954df650a2.gif}
\InputFile
The first line contains one integer $n~(0 < n \le 10^5)$ --- number of nodes in the tree. Next $n - 1$ lines contain $n - 1$ edges of that tree. Each line contains a pair $(u, v)$ means there is an edge between node $u$ and node $v~(1 \le u, v \le n)$.
\OutputFile
Print number of nodes in the satisfied vertex set on one line.
Input example #1
6 1 2 1 3 2 4 2 5 1 6
Output example #1
2