선로 감시기

아래 그림과 같이 트리 형태의 지하철 노선이 있다. 트리의 노드는 지하철 역을 나타내고 에지는 선로가 된다. (트리는 사이클이 없고 연결된 그래프를 말한다.) 각 노드는 숫자로 구분되고 각 선로의 상태를 감시하기 위한 선로 감시기를 역에 설치하려고 한다. 역에 설치된 감시기는 이 역에 인접한 모든 선로를 감시할 수 있다. 최소 개수의  감시기를 설치해서 모든 선로를 감시하려고 한다.

위 그림의 예에서 3번 역과 1번 역을 잇는 선로를 감시하기 위해서는 3번 역이나 1번 역 둘 중에 최소한 하나의 감시기를 설치하여야 한다. 1, 7, 6번 역에 감시기를 설치하면 모든 선로를 감시할 수 있다. 감시기를 두개 설치하여서는 감시할 수 없는 선로가 항상 존재하므로, 감시기 3개가 최소가 된다.

각 역과 이들 역을 잇는 선로가 주어질 때, 필요한 감시기의 최소 개수를 구하는 프로그램을 작성하시오. 프로그램 이름은 guard.cpp, 실행 파일의 이름은 guard.exe, 프로그램 설명 파일 이름은 guard.hwp로 하고, 프로그램의 실행시간은 1초를 초과할 수 없다. 부분 점수는 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT로 한다. 입력 파일의 첫째 줄에 지하철 역의  개수를 나타내는 정수 이 주어진다. 지하철 역은 1부터 까지 번호가 매겨져 있다. 이후 개의 줄에는 한 줄에 하나씩 선로로 이어진 두 지하철 역을 나타내는 두 정수가 주어진다. 입력되는 두 정수 사이에는 빈칸이 있다.

2004 가을학기 문제해결기법	문제 #7

출력 형식

출력 파일의 이름은 OUTPUT.TXT로 한다. 첫째 줄 한 줄에 모든 선로를 감시하는데 필요한 최소의 감시기 개수를 나타내는 정수를 출력한다.

입력과 출력의 예

입력(input.txt)

8

3 1

2 1

5 6

6 7

7 4

7 8

1 7

출력(output.txt)

3