Phân nhóm xung đột

Bối cảnh và bài toán

Có n nhân sự và m cặp xung đột. Ta muốn chia mọi người thành hai nhóm sao cho không có cặp xung đột nào nằm cùng nhóm.

Yêu cầu

Xác định việc chia hai nhóm có khả thi hay không.

Input

Dòng đầu n, m; tiếp theo m cặp u, v.

Output

In "YES" nếu có thể chia, ngược lại "NO".

Ràng buộc

• 1 <= n <= 2*10^5
• 0 <= m <= 2*10^5 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

5 3
1 2
1 3
4 5

Output

YES

Giải thích. Có thể chia hai nhóm khi toàn bộ cạnh nối hai màu khác nhau; chu trình lẻ gây mâu thuẫn.

Ví dụ 2

Input

3 3
1 2
2 3
3 1

Output

NO

Giải thích. Có thể chia hai nhóm khi toàn bộ cạnh nối hai màu khác nhau; chu trình lẻ gây mâu thuẫn.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Building Teams. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.