Phân chia hai phe
Points
20
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề 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. Thầy giáo muốn chia $N$ học sinh vào 2 nhóm sao cho không có cặp học sinh nào không thích nhau nằm cùng một nhóm (tức là kiểm tra xem đồ thị có phải là đồ thị hai phía hay không).
Dữ liệu vào
- Dòng đầu tiên 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
- In ra
YESnếu có thể chia thành 2 nhóm thỏa mãn, ngược lại in raNO.
Ví dụ
| Input | Output |
|---|---|
| 4 4 1 2 2 3 3 4 4 1 |
YES |
| 3 3 1 2 2 3 3 1 |
NO |
Giới hạn
- $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$.
Community Discussion