Competitions

# 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.

#### Input

The first line contains one integer **n** (**0** < **n** ≤ **100000**) – 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** ≤ **u**, **v** ≤ **n**).

#### Output

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