Cell Phone Network#1766
Farmer John has decided to give each of his cows a cell phone in hopes of encouraging their social interaction. This, however, requires him to set up cell phone towers on his (1 \leq N \leq 100\,000) pastures (conveniently numbered to ) so they can all communicate.
Exactly N - 1 pairs of pastures are adjacent, and for any two pastures and (1 \leq A \leq N; 1 \leq B \leq N; A \neq B), there is a sequence of adjacent pastures such that is the first pasture in the sequence and is the last. Cell phone towers can be placed only in pastures, and each tower has enough range to serve the pasture it is placed on, as well as 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 . The next N - 1 lines each contain two space-separated integers, describing a pair of adjacent pastures.
Output a single integer—the minimum number of towers needed.
Example 1