Phân nhóm đồ thị hai phía

Buổi 73-74 — Virtual CF Graphs
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho đồ thị vô hướng gồm $n$ đỉnh và $m$ cạnh. Bạn cần tô màu mỗi đỉnh bằng một trong hai màu (Trắng hoặc Đen) sao cho không có hai đỉnh kề nhau nào cùng màu. Nếu tồn tại cách tô hợp lệ, hãy tìm số lượng đỉnh được tô màu Trắng lớn nhất có thể. Nếu đồ thị không thể tô hai màu, in ra -1.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $n, m$ ($1 \le n \le 10^5, 0 \le m \le 2 \cdot 10^5$).
  • $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le n$).
Dữ liệu ra
  • Một số nguyên duy nhất là số đỉnh màu Trắng tối đa, hoặc -1.
Ví dụ
Input Output
5 3
1 2
1 3
4 5
3
Giới hạn
  • $1 \le n \le 10^5, 0 \le m \le 2 \cdot 10^5$
Draft saved