Fire Station Placement on Mars

In the year 2020, humans established a vast network of bases on Mars. There are \(n\) bases connected by exactly \(n-1\) roads forming a tree structure (i.e. there is exactly one unique path between any two bases). The distance between any two bases \(A\) and \(B\) is defined as \(d\) if the minimum number of roads to be traversed is \(d\).

Due to Mars' extremely dry conditions, wildfires are frequent. To combat this, fire stations are to be built at some of these bases. A fire station built at a base can cover all bases within a distance of at most \(2\) (including the base itself). Your task is to determine the minimum number of fire stations required so that every base is within distance \(2\) of at least one fire station.

Note: The input guarantees that the bases and roads form a tree.

inputFormat

The first line contains an integer \(n\) (number of bases). Each of the following \(n-1\) lines contains two integers \(u\) and \(v\) indicating that there is a road connecting base \(u\) and base \(v\). It is guaranteed that any base is reachable from any other base using the provided roads.

outputFormat

Output a single integer, the minimum number of fire stations required so that every base is within distance \(2\) of a fire station.

sample

3
1 2
2 3

1