Cell Phone Network#10156
Farmer John has decided to give each of his cows a cell phone in the hope of encouraging social interaction among them. However, this requires him to install cell phone towers in his pastures, conveniently numbered 1, \ldots, n, so that all the cows can communicate.
Exactly n - 1 pairs of pastures are adjacent. Furthermore, for any two distinct pastures and , there is a sequence of adjacent pastures that starts at and ends at .
Farmer John can only install cell phone towers in the pastures. Each tower provides cell phone service to the pasture where it is installed and to all pastures adjacent to it.
Help Farmer John determine the minimum number of towers he must install to provide cell phone service to every pasture.
The first line contains one integer n~(1 \le n \le 10^4). Each of the next n - 1 lines contains two integers and b~(1 \le a, b \le n, a \ne b), indicating that pastures and are adjacent.
Print one integer indicating the minimum number of towers that must be installed.
Example 1