Cell Phone Network

Farmer John has decided to give each of his cows a cell phone to encourage their social interaction. To let the cows communicate, he must install cell phone towers on his $N$ pastures (conveniently numbered $1$ through $N$).

Exactly $N-1$ pairs of pastures are adjacent, and for any two pastures $A$ and $B$ there is a sequence of adjacent pastures leading from $A$ to $B$. In other words, the pastures form a tree.

Towers can only be placed on pastures. A tower placed on a pasture provides service to that pasture and to every pasture adjacent to it.

Determine the minimum number of towers Farmer John must install so that every pasture receives cell phone service.

Constraint: $1 \le N \le 10000$.

• Line 1: a single integer $N$ ($1 \le N \le 10000$).
• Lines 2 to $N$: each line contains two space-separated integers $A$ and $B$ describing a pair of adjacent pastures ($1 \le A, B \le N$, $A \ne B$).

• A single integer: the minimum number of towers needed so that every pasture receives service.

The picture below shows one example with $5$ pastures whose adjacencies form a tree.

   4  2
   |  |
1--3--5

A tower on pasture $3$ serves pastures $1, 3, 4$, and $5$; adding one more tower on pasture $2$ (or $5$) covers the rest. Since each tower serves itself and its neighbors, the goal is to place towers so that their combined coverage reaches every pasture.