문제
바닷가에 인접한 어떤 마을에서는 해일이 언제 닥칠지 몰라 늘 불안하다. 그래서 모든 사람들에게 즉시 위험을 알릴 수 있도록 비상벨을 설치하기로 했다.
우선 각 집마다 벨을 한 개씩 설치하고 모든 벨과 벨이 연결될 수 있도록 N-1개의 선을 연결한다. 그리고 경찰서에서 어떤 집의 벨과 연결하여 경찰서에서 신호를 보내면 모든 집에 연결된 벨이 울리도록 하는 것이다. 그런데 문제가 생기고 말았다. 경찰서와 직접 연결된 벨과 그 벨에서 연결된 다음 벨까지는 문제없이 울리는데 그 다음에는 전압이 약해져서 그 벨에 연결된 벨은 울리지 않는 것이다. 즉 경찰서와 연결된 벨과 그 벨로부터 연결된 벨까지는 울리지만 그 다음에 연결된 벨부터는 울리지 않는 것이다. 이것을 해결할 수 있는 장비가 부족한 관계로 부득이 모든 벨이 울릴 수 있도록 경찰서에서 여러 집의 벨을 선정하여 직접 연결을 하기로 하였다.
경찰서와 각 집의 벨을 연결하기 위해서는 비용이 많이 들기 때문에 가능하면 최소한의 벨에 연결하려고 한다. 모든 벨을 울리기 위해 경찰서와 연결해야하는 최소의 벨은 모두 몇 개인지 출력하는 프로그램을 작성하라.
입력
첫 줄에 마을의 모든 집의 수 N이 입력된다. (1 ≤ N ≤ 10,000)
둘째 줄부터 N-1개의 줄에 걸쳐 집과 집 사이의 벨의 연결 상태를 나타내는 두 수가 주어진다.
두 수는 각각 집의 번호를 나타내며, 그 두 집의 벨이 서로 연결되어 있다는 것을 의미한다. 집의 번호는 1번부터 N번까지 이다.
출력
경찰서와 직접 연결해야 하는 최소 벨의 수를 출력한다.
예제
5
3 2
5 4
1 2
2 5
2
출처
2014 ICT Award KOREA
로그인해야 코드를 작성할 수 있어요.