12978번 - 스크루지 민호 2

구두쇠로 유명한 스크루지 민호가 다스리는 천나라가 있다. 천나라에는 N 개의 도시들이 있는데 각각의 도시들 사이에는 양방향 도로로 이어져 있다. 민호는 도시를 세울 때 최소한의 비용만을 들이고 싶어서 N - 1 개의 도로를 이용해 모든 도시들 사이에는 단 한개의 경로만이 존재하도록 도시를 세웠다.

도시를 건설 한 뒤 이번에는 경찰서를 세우려고 했지만 모든 도시에 경찰서를 걸설하기 아까웠던 민호는 몇몇 도시에 경찰서들을 세우지 않기로 했다. 하지만 경찰이 감시하지 못하는 도시들과 도로들이 생기게 된다면 시민들이 반란을 일으킬 수도 있다고 생각한 민호는 최소한의 도시에 경찰서를 세워 모든 도로들과 도시들을 감시하게 하고 싶어졌다.

한 도시에 경찰서를 세우면 해당 도시와 그 도시에 연결된 양방향 도로들로 연결된 도시들을 감시할 수 있다.

천나라에 있는 도시의 수와 도로들의 연결 상태가 주어질 때 최소 몇개의 도시들에 경찰서를 세워야 모든 도시들과 도로들을 감시할 수 있게 하는지 구해보자.

첫째 줄에는 천나라에 있는 도시의 수 N (2 ≤ N ≤ 100,000) 이 주어진다.  다음 N - 1 줄에 걸쳐 도시들의 연결 상태가 주어진다.

각각의 줄에는 공백을 기준으로 세개의 숫자가 u, v (1 ≤ u, v ≤ N) 가 주어지는데 이는 도시 u와 v가 양방향 도로로 연결이 되어 있다는 것을 의미한다.

첫째 줄에 민호가 경설사를 건설해야 하는 최소 도시의 수를 출력한다.