트리 게임

시간 제한1초메모리 제한512 MB

요약

모든 간선이 흰색인 트리에서 끝점이 리프이고 지나는 간선이 모두 흰색인 단순 경로를 골라 그 간선을 검게 칠하는 과정을 반복할 때, 모든 간선을 칠하기 위해 필요한 최소 경로 수를 구한다.

난이도: 보통10점 중 7점
유형: 트리, DFS, 그리디, 동적 계획법
정답자: 아직 제출이 없습니다

문제

트리의 간선에 색을 칠하는 다음 게임을 생각해 보자.

트리가 주어진다. 처음에 모든 간선의 색은 흰색이다. 유효 경로란 모든 간선이 흰색인 단순 경로 중 양 끝점이 트리의 리프인 경로를 말한다. 이 게임의 각 단계에서 유효 경로를 하나 골라 그 경로의 모든 간선을 검은색으로 칠할 수 있다. 더 이상 유효 경로를 찾을 수 없을 때까지 게임을 끝낼 수 없다.

이 게임의 목적은 최소 횟수의 단계로 게임을 끝내는 것이다. 주어진 트리에 대해 게임을 끝내는 데 필요한 최소 단계 수를 구하시오.

입력

첫째 줄에 트리의 노드 수 $N$ 이 주어진다.

다음 $N-1$ 개 줄에 각각 두 정수 $x$ 와 $y$ 가 주어지며, 이는 $x$ 번 노드와 $y$ 번 노드가 간선으로 연결되어 있음을 나타낸다. 노드는 $1$ 부터 $N$ 까지 번호가 매겨져 있다.

출력

주어진 트리에서 게임을 끝내는 데 필요한 최소 단계 수를 정수로 출력한다.

제한

$2 \le N \le 10^5$
$1 \le x, y \le N$
주어진 그래프는 트리이다.

예제2

예제 1
입력
```
7
1 2
1 3
2 4
2 5
3 6
3 7
```
예상 출력
```
1
```
예제 2
입력
```
9
1 2
1 3
2 4
2 5
3 6
3 7
8 2
9 3
```
예상 출력
```
3
```