휴대폰 네트워크

John 농부는 소들의 사회적 교류를 장려하기 위해 각 소에게 휴대폰을 나눠 주기로 했다. 그러려면 소들이 서로 통신할 수 있도록 $N$개의 목초지(편의상 $1$번부터 $N$번까지 번호가 붙어 있다)에 중계탑을 세워야 한다.

정확히 $N-1$쌍의 목초지가 서로 인접해 있으며, 임의의 두 목초지 $A$와 $B$에 대해 $A$에서 출발하여 인접한 목초지들을 따라 이동해 $B$에 도달하는 경로가 항상 존재한다. 즉, 목초지들은 하나의 트리를 이룬다.

중계탑은 목초지에만 세울 수 있고, 어떤 목초지에 세운 중계탑은 그 목초지 자신과 그 목초지에 인접한 모든 목초지에 통신을 제공한다.

모든 목초지에 통신을 제공하기 위해 세워야 하는 중계탑의 최소 개수를 구하여라.

제약: $1 \le N \le 10000$.

• 첫째 줄: 정수 $N$ ($1 \le N \le 10000$)
• 둘째 줄부터 $N$번째 줄까지: 각 줄에 인접한 두 목초지의 번호 $A$와 $B$가 공백으로 구분되어 주어진다 ($1 \le A, B \le N$, $A \ne B$).

• 첫째 줄에 모든 목초지에 통신을 제공하기 위해 세워야 하는 중계탑의 최소 개수를 출력한다.

아래 그림은 목초지가 $5$개이고 인접 관계가 트리를 이루는 한 예이다.

   4  2
   |  |
1--3--5

$3$번 목초지에 중계탑을 세우면 $1, 3, 4, 5$번 목초지에 통신이 제공되고, 여기에 $2$번(또는 $5$번) 목초지에 중계탑을 하나 더 세우면 남은 목초지까지 모두 덮을 수 있다. 이처럼 각 중계탑이 자신과 인접한 목초지를 덮는다는 점을 이용해, 전체 목초지를 덮도록 중계탑을 배치하는 것이 핵심이다.