[tree] cut The Tree

Cho một đồ thị dạng cây n đỉnh, các cạnh được biểu diễn bằng ma trận 2 chiều edges, bạn hãy bỏ đi số cạnh nhiều nhất sao cho với mỗi đồ thị mới được tạo ra đều có số đỉnh là chẵn. Nếu đồ thị ban đầu có số đỉnh lẻ và không tồn tại cách bỏ để số đỉnh các đồ thị mới là chẵn thì output ra -1.

Ví dụ:

• Cho n = 4, edges = [[1, 2], [2, 3], [3, 4]], output là cutTheTree(n, edges) = 1.
  Giải thích:
  
  • Có thể bỏ đi cạnh nối giữa đỉnh 2 và 3. Sau khi bỏ sẽ tạo thành 2 đồ thị con và 2 đồ thị này nếu có số đỉnh chẵn.
• Cho n = 3, edges = [[1, 2], [1, 3]], output là cutTheTree(n, edges) = -1.
  Giải thích:
  • Đồ thị ban đầu có số đỉnh là lẻ và không tồn tại cách cắt.
• Cho n = 2, edges = [[1, 2]], output là cutTheTree(n, edges) = 0.

Đầu vào/Đầu ra

• [Giới hạn thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, JS và Go

• [Đầu vào] Integer n
  1 <= n <= 1000

• [Đầu vào] Matrix of integer edges.
  edges.size = n - 1
1 <= edges[i][j] <= n

• [Đầu ra] Integer