나무

시간 제한2초메모리 제한256 MB

요약

정점 하나에서 시작해 간선 삭제와 차수가 1 이하인 정점에 두 잎을 추가하는 연산만으로 주어진 트리를 만드는 최소 연산 수를 구하고, 불가능하면 -1을 출력한다.

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

문제

분재를 키우는 기술은 2000년이 넘는 역사를 가지고 있으며, 그동안 다양한 스타일과 기법이 개발되었다. 이 문제에서도 나무를 키워야 하지만, 조금 다른 의미에서이다.

나무는 사이클이 없는 무방향 연결 그래프이다. 처음에는 정점 하나로 이루어진 나무가 있다. 나무에 사용할 수 있는 연산은 두 가지이다. 간선 하나를 제거하고 두 부분 중 아무 것이나 남기는 연산, 그리고 새로운 정점 두 개를 추가하고 이전에 인접한 정점이 하나 이하였던 정점에 연결하는 연산이다. 주어진 나무를 얻기 위해 필요한 최소 연산 횟수는 얼마인가?

입력

첫 번째 줄에는 정수 n이 주어진다 (1 ≤ n ≤ 105). 다음 n - 1개의 줄에는 각각 두 수 ui, vi가 주어지며, 이는 나무의 간선을 나타낸다 (1 ≤ ui, vi ≤ n, 모든 i에 대해 1 ≤ i ≤ n - 1). 주어진 그래프는 나무임이 보장된다.

출력

이러한 나무를 만들 수 없다면 -1을 출력한다. 그렇지 않으면 주어진 나무를 얻기 위해 필요한 최소 연산 횟수를 출력한다.

예제3

예제 1
입력
```
2
1 2
```
예상 출력
```
2
```
예제 2
입력
```
3
1 2
2 3
```
예상 출력
```
1
```
예제 3
입력
```
5
1 2
1 3
1 4
1 5
```
예상 출력
```
-1
```