Phân chia hai phe đối lập
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Trong một lớp học có $N$ học sinh và $M$ cặp học sinh không thích nhau. Giáo viên muốn chia toàn bộ $N$ học sinh thành hai nhóm sao cho không có hai học sinh nào không thích nhau bị xếp vào cùng một nhóm. Hãy kiểm tra xem có thể thực hiện được việc chia nhóm như vậy hay không.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $M$.
- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ cho biết học sinh $u$ và $v$ không thích nhau.
Dữ liệu ra
- In ra
YESnếu có thể chia thành hai nhóm hợp lệ, ngược lại in raNO.
Ví dụ
| Dữ liệu vào | Dữ liệu ra |
|---|---|
| 4 4 1 2 2 3 3 4 4 1 |
YES |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le M \le 2 \cdot 10^5$
Community Discussion