Cây chẵn

Xem dạng PDF

Gửi bài giải

Điểm: 0,10 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C++, Pascal, Python

Cho một cây có n đỉnh, hãy xác định số lượng cạnh lớn nhất có thể xóa bỏ để toàn bộ các vùng liên thông còn lại có kích thước chẵn.

Input

  • Dòng đầu tiên chứa số nguyên dương n105.
  • n1 dòng tiếp theo chứa 2 số u,v(u,vn) là các cạnh của cây.

Output

  • In ra một số nguyên số cạnh có thể xóa
  • Nếu không thể có cách cắt thỏa mãn, in ra -1.

    Sample Test 1

Input:

Copy
4
2 4
4 1
3 1

Output:

Copy
1

Sample Test 2

Input:

Copy
10
7 1
8 4
8 10
4 7
6 5
9 3
3 5
2 10
2 5

Output:

Copy
4