Chia đội thi đấu
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề 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$
Community Discussion