해결한 사람
0
명
정답률
0.00
%
시간 제한
1000
ms
메모리 제한
245
MB
n개의 정점으로 이루어진 트리가 주어진다.
남아 있는 모든 연결 요소의 크기가 짝수가 되도록 제거할 수 있는 간선 수의 최댓값을 구한다.
첫째 줄에는 트리의 크기를 나타내는 정수 n (1 ≤ n ≤ )이 주어진다.
다음 n - 1개의 줄에는 각각 두 정수 u, v (1 ≤ u, v ≤ n)가 주어지며, i-th번째 간선으로 연결된 정점들을 나타낸다.
주어진 간선들이 트리를 이룬다는 것이 보장된다.
모든 연결 요소의 크기가 짝수가 되도록 제거할 수 있는 간선 수의 최댓값 k를 출력한다. 이 조건을 만족하도록 간선을 제거하는 것이 불가능하면 -1을 출력한다.
4
2 4
4 1
3 1
1
2
1 2
0
10
7 1
8 4
8 10
4 7
6 5
9 3
3 5
2 10
2 5
4
첫 번째 예제에서는 정점 1과 4 사이의 간선을 제거할 수 있다. 그러면 그래프에는 각각 두 개의 정점을 가진 연결 요소가 두 개 생긴다.
두 번째 예제에서는 모든 연결 요소의 정점 수가 짝수가 되도록 간선을 제거할 수 없으므로 답은 -1이다.