Phân chia phe phái cân bằng
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề 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
-1nế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$.
Community Discussion