Một đồ thị hai phía (bipartite) là đồ thị mà tập đỉnh có thể chia thành hai nhóm sao cho mọi cạnh nối một đỉnh nhóm này với một đỉnh nhóm kia. Tương đương: đồ thị tô được bằng 2 màu (không có chu trình lẻ).
Cho đồ thị vô hướng, hãy kiểm tra nó có phải hai phía hay không bằng cách tô 2 màu theo BFS/DFS.
Dòng đầu gồm hai số n m — số đỉnh và số cạnh. m dòng sau, mỗi dòng hai số u v là một cạnh vô hướng (đỉnh đánh số từ 1).
1 <= n <= 1000; 0 <= m <= 5000.
In YES nếu đồ thị hai phía, ngược lại in NO.
Ví dụ:
Đầu vào:
4 4
1 2
2 3
3 4
4 1
Đầu ra:
YES
Giải thích:
Đang tải editor...