Description

Farmer John wants all his cows to use cell phones so that they can communicate. He needs to build several cell towers among $N$ pastures. A tower provides coverage to the pasture it is placed on and to any pasture adjacent to it. You are given $N-1$ adjacency pairs $(A, B)$ between pastures. What is the minimum number of towers required so that every pasture has coverage?

Input Format

Line 1: an integer $N$.

Lines 2 through $N$: each line contains two integers separated by a space, giving one adjacent pair of pastures $A$ and $B$.

Output Format

A single integer, the minimum number of towers to install.

5
1 3
5 2
4 3
3 5

2

Hint

For all testdata, $1 \leq N \leq 10^4$, $1 \leq A, B \leq N$, $A \neq B$.

Translated by ChatGPT 5