Guard Placement in the Kingdom

In the Kingdom there are (n) cities connected by (n-1) roads, forming a tree structure. The ruler wants to secure all roads by assigning guards to some cities. A guard placed in a city secures all the roads incident to that city. Your task is to determine the minimum number of guards needed so that every road is monitored.

Formally, given an undirected tree (T) with (n) vertices and (n-1) edges, find a vertex cover of minimum size. A vertex cover is a set of vertices such that each edge has at least one of its endpoints in the set. The answer is the size of such a minimum vertex cover.

inputFormat

The input is given via standard input. The first line contains an integer (n) representing the number of cities. The following (n-1) lines each contain two integers (u) and (v) indicating that there is a road between city (u) and city (v). It is guaranteed that the cities form a tree.

outputFormat

Output a single integer, which is the minimum number of guards required to secure all the roads. The output should be printed on standard output.## sample

4
1 2
1 3
1 4

1