favorite We need a little bit of your help to keep things running, click on this banner to learn more

IOI Preparation - Trees

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.



The first line contains one integer n (0 < n100000) – 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 (1u, vn).


Print number of nodes in the satisfied vertex set on one line.

Time limit 1 second
Memory limit 128 MiB
Input example #1
1 2
1 3
2 4
2 5
1 6
Output example #1