Cell Phone Tower Coverage

Farmer John has a set of N pastures (numbered from 1 to N) connected by exactly N-1 pairs of adjacent pastures forming a tree. In order for his cows to communicate via cell phones, Farmer John needs to install a minimal number of cell phone towers; however, a tower placed in a pasture covers that pasture and all directly adjacent pastures.

Your task is to determine the minimum number of towers required such that every pasture receives cell phone service.

Note: It is guaranteed that there is a unique path between any two pastures.

The problem can be expressed as finding the minimum dominating set in a tree.

Input Format: The first line contains an integer N (1 ≤ N ≤ 10,000) representing the number of pastures. Each of the next N-1 lines contains two integers A and B (1 ≤ A, B ≤ N, A ≠ B), indicating that pasture A is adjacent to pasture B (and vice versa).

Output Format: A single integer, the minimum number of towers needed to cover all the pastures.

The key observation is that the problem can be solved by a greedy Depth First Search (DFS) strategy on a tree. During the DFS, each node can be in one of the following states:

• 0: not covered by any tower.
• 1: a tower is installed at this node.
• 2: covered by a tower installed in one of its adjacent nodes.

By processing the tree from the leaves upward, you can decide where to place a tower to ensure that all pastures (nodes) are covered while minimizing the number of towers used. In case the root remains uncovered at the end of the DFS, add an extra tower at the root.

inputFormat

The input starts with an integer N (1 ≤ N ≤ 10,000), the number of pastures. The following N-1 lines each contain two integers A and B (1 ≤ A, B ≤ N) representing an undirected edge between pastures A and B.

Example:

3
1 2
1 3

outputFormat

Output a single integer indicating the minimum number of cell phone towers required to ensure that every pasture is covered.

Example:

1

sample

1

1

</p>