Farmer John donne un téléphone à chaque vache pour favoriser les échanges. Il faut des antennes sur les $N$ pâturages ($1 \le N \le 10,000$), numérotés $1,\ldots,N$, pour communiquer.

Exactement $N-1$ paires sont voisines ; pour tous $A$, $B$ ($1 \le A \le N; 1 \le B \le N; A \ne B$), une séquence de pâturages adjacents relie $A$ à $B$. Une antenne ne se place que dans un pâturage et couvre celui-ci et tous ses voisins.

Trouvez le minimum d’antennes couvrant tous les pâturages.

Entrée

Lisez l’entrée standard.

• Ligne 1 : entier $N$.
• Lignes $2,\ldots,N$ : une paire voisine, entiers $A$, $B$ séparés par un espace.

Sortie

Écrivez sur la sortie standard.

• Ligne 1 : entier, nombre minimal d’antennes.

Exemples

Entrée 1

5
1 3
5 2
4 3
3 5

Sortie 1

2

Remarque

5 pâturages : 1 et 3, 5 et 2, 4 et 3, 3 et 5 sont voisins. La géométrie est ainsi (ou similaire) :

               4  2
               |  |
            1--3--5

Placez les antennes en 2 et 3, ou en 3 et 5.

Auteur du problème : Jeffrey Wang, 2007