트리 최소 버텍스 커버

문제

N개의 정점으로 이루어진 트리에서 최소 버텍스 커버의 크기를 구하라.

버텍스 커버란, 트리의 모든 간선에 대하여 그 간선의 양 끝점 중 적어도 하나가 포함된 정점 집합을 뜻한다. 트리는 정점이 N개, 간선이 N-1개인 연결 그래프이며 사이클이 없다.

입력

첫째 줄에 정점의 개수 N이 주어진다.
둘째 줄부터 N-1개의 줄에 걸쳐 간선의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 간선의 양 끝점을 나타내는 두 정수 u와 v가 공백으로 구분되어 주어진다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ u, v ≤ N
• 주어지는 그래프는 트리이다. (사이클이 없는 연결 그래프)

출력

주어진 트리의 최소 버텍스 커버의 크기를 출력한다.

예제 입력 1

3
1 2
2 3

예제 출력 1

1

예제 입력 2

4
1 2
1 3
1 4

예제 출력 2

1