Phân chia phe phái cân bằng

Buổi 24 — Mock Contest Phase 1
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Một mạng lưới gồm $N$ điệp viên đánh số từ $1$ đến $N$ và $M$ mối quan hệ đối địch hai chiều. Bạn cần phân chia tất cả $N$ điệp viên vào hai phe Đỏ và Xanh sao cho không có hai điệp viên đối địch nhau nào nằm cùng một phe.

Nếu không thể phân chia hợp lệ, hãy in ra -1. Ngược lại, gọi $R$ là số người phe Đỏ và $B$ là số người phe Xanh ($R + B = N$). Hãy tìm giá trị nhỏ nhất có thể của $|R - B|$.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N, M$ ($1 \le N \le 2000$, $0 \le M \le 10^4$).
  • $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$) mô tả cặp điệp viên đối địch.
Dữ liệu ra
  • Một số nguyên duy nhất là giá trị nhỏ nhất của $|R - B|$, hoặc -1 nếu không thể phân chia.
Ví dụ
Input Output
5 3
1 2
2 3
4 5
1
3 3
1 2
2 3
3 1
-1
Giới hạn
  • $1 \le N \le 2000$, $0 \le M \le 10^4$.
Draft saved