Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Có $N$ học sinh và $M$ cặp học sinh không thích làm việc cùng nhau. Ban tổ chức muốn chia $N$ học sinh thành $2$ đội (mỗi đội có thể có từ $0$ đến $N$ người) sao cho không có hai học sinh nào ghét nhau bị xếp vào cùng một đội.

Hãy kiểm tra xem có thể thực hiện được việc chia đội như vậy hay không.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N, 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 ở cùng đội.

Dữ liệu ra

In ra YES nếu có thể chia thành $2$ đội thỏa mãn điều kiện, ngược lại in ra NO.

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$
  • $1 \le u, v \le N$, $u \ne v$
Draft saved