Xét đơn đồ thị vô hướng gồm đỉnh. Giữa hai đỉnh bất kỳ luôn tồn tại đường đi (trực tiếp hoặc qua các đỉnh khác). Đồ thị có tính chất đặc biệt: Gọi là tập các đỉnh có đường nối trực tiếp với , khi đó với hai đỉnh và là bất kì thuộc thì tồn tại đường đi từ tới trực tiếp hoặc qua các đỉnh thuộc , nhưng không qua .
Yêu cầu: Cho trong đó là số đỉnh, là số cạnh mô tả đồ thị thỏa mãn điều kiện đề bài, hãy tô màu đồ thị bằng ba màu R, B, G thỏa mãn điều kiện không có hai đỉnh nào có đường nối trực tiếp cùng tô một màu.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và ;
Dòng thứ trong dòng sau chứa hai số nguyên cho biết có cạnh nối trực tiếp giữa hai đỉnh của đồ thị.
Kết quả:
Dòng đầu tiên chứa thông báo YES hoặc NO thể hiện có hoặc không có cách tô thỏa mãn điều kiện;
Nếu tồn tại cách tô thì dòng thứ hai chứa xâu mô tả cách tô.
