#1565. COLOR3 - Tô màu các vòng tròn

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: Trình chấm ngoài
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho n vòng tròn trên giấy, đánh số các vòng tròn từ 1 đến n , nối một số vòng tròn với nhau bằng các cung, sau đó tô mỗi vòng tròn bằng một trong số 3 màu đỏ (R), xanh (G) và lam (B). Người ta muốn tô lại mỗi vòng tròn bằng một màu khác và đảm bảo sao cho không có hai vòng tròn cùng màu được nối trực tiếp với nhau.

Yêu cầu: Cho biết số lượng vòng tròn n , số cung nối m dưới dạng các cặp số nguyên (i, j) cho biết đường tròn i được nối với đường tròn j và cho biết màu của mỗi đường tròn dưới dạng xâu các ký tự {R, B, G}. Hãy chỉ ra màu của các vòng tròn sau khi tô lại hoặc đưa ra thông báo Impossible nếu không thể tô lại được.

Dữ liệu:

  • Dòng đầu tiên chứa hai số nguyên n m ;
  • Dòng thứ hai chứa xâu n ký tự {R, B, G}, ký tự thứ i xác định màu vòng tròn i ;
  • m dòng sau, mỗi dòng chứa hai số nguyên i, j cho biết vòng tròn i được nối với vòng tròn j .

Kết quả:

  • Xâu n ký tự xác định màu các vòng tròn sau khi tô lại hoặc thông báo Impossible.

Ví dụ:

Dữ liệu:

4 5
RRRG
1 3
1 4
3 4
2 4
2 3

Kết quả:

GGBR

Giới hạn:

  • Subtask \#1: 𝑛 ≤ 20 ;
  • Subtask \#2: 𝑛 ≤ 1000 .