Farmer John gibt jeder Kuh ein Handy, um soziale Kontakte zu fördern. Zur Kommunikation braucht er Funkmasten auf seinen $N$ Weiden ($1 \le N \le 10,000$), nummeriert $1,\ldots,N$.

Genau $N-1$ Paare sind benachbart; zwischen beliebigen $A$, $B$ ($1 \le A \le N; 1 \le B \le N; A \ne B$) gibt es eine Folge benachbarter Weiden von $A$ nach $B$. Masten dürfen nur auf Weiden stehen und versorgen die eigene und alle benachbarten Weiden.

Bestimme die minimale Mastzahl zur Versorgung aller Weiden.

Eingabe

Lies von der Standardeingabe.

• Zeile 1: ganze Zahl $N$.
• Zeilen $2,\ldots,N$: benachbartes Paar, ganze Zahlen $A$, $B$, durch ein Leerzeichen getrennt.

Ausgabe

Schreibe auf die Standardausgabe.

• Zeile 1: ganze Zahl, minimale Mastzahl.

Beispiele

Eingabe 1

5
1 3
5 2
4 3
3 5

Ausgabe 1

2

Hinweis

5 Weiden: 1 und 3, 5 und 2, 4 und 3, 3 und 5 sind benachbart. Geometrisch sieht es so (oder ähnlich) aus:

               4  2
               |  |
            1--3--5

Masten können auf 2 und 3 oder auf 3 und 5 stehen.

Aufgabenautor: Jeffrey Wang, 2007