Con của Cameron và Jamie sắp tròn 3 tuổi! Tuy giờ đây đứa trẻ đã tự lập hơn, việc sắp xếp các hoạt động cho con và những công việc thiết yếu trong gia đình vẫn là một thử thách đối với hai người.

Cameron và Jamie có một danh sách gồm \(N\) hoạt động cần thực hiện trong ngày. Mỗi hoạt động diễn ra trong một khoảng thời gian xác định. Họ cần giao mỗi hoạt động cho một trong hai người sao cho không ai phải phụ trách hai hoạt động chồng lấn nhau. Một hoạt động kết thúc tại thời điểm \(t\) không được coi là chồng lấn với một hoạt động khác bắt đầu tại thời điểm \(t\).

Ví dụ, giả sử Jamie và Cameron cần phụ trách 3 hoạt động: một hoạt động từ 18:00 đến 20:00, một hoạt động khác từ 19:00 đến 21:00 và một hoạt động nữa từ 22:00 đến 23:00. Một cách phân công là để Jamie phụ trách hoạt động từ 19:00 đến 21:00, còn Cameron phụ trách hai hoạt động kia. Một lịch hợp lệ khác là để Cameron phụ trách hoạt động từ 18:00 đến 20:00 và Jamie phụ trách hai hoạt động còn lại. Lưu ý rằng hai hoạt động đầu tiên chồng lấn trong khoảng từ 19:00 đến 20:00, vì vậy không thể giao cả hai hoạt động đó cho cùng một người.

Cho thời điểm bắt đầu và kết thúc của mỗi hoạt động, hãy tìm một lịch bất kỳ sao cho cùng một người không phải phụ trách các hoạt động chồng lấn, hoặc cho biết điều đó là không thể.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên \(N\), là số hoạt động cần phân công. Sau đó là \(N\) dòng nữa. Dòng thứ \(i\) trong số này (đánh số từ 1) chứa hai số nguyên \(S_i\) và \(E_i\). Hoạt động thứ \(i\) bắt đầu đúng \(S_i\) phút sau nửa đêm và kết thúc đúng \(E_i\) phút sau nửa đêm.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là IMPOSSIBLE nếu không có lịch hợp lệ theo các quy tắc trên; nếu có, y là một chuỗi gồm đúng \(N\) ký tự. Ký tự thứ \(i\) của y phải là C nếu hoạt động thứ \(i\) được giao cho Cameron trong lịch đề xuất, và là J nếu hoạt động đó được giao cho Jamie.

Nếu có nhiều lời giải, bạn có thể in ra bất kỳ lời giải nào. Thông tin về việc có nhiều lời giải sẽ không được nhắc lại một cách tường minh trong các bài còn lại của cuộc thi năm 2020.

Ràng buộc

• \(1 \le T \le 100\).
• \(0 \le S_i < E_i \le 24 \times 60\).

Phân nhóm

Test Set 1 (phản hồi kết quả đầy đủ):

• \(2 \le N \le 10\).

Test Set 2 (phản hồi kết quả đầy đủ):

• \(2 \le N \le 1000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
3
360 480
420 540
600 660
3
0 1440
1 3
2 4
5
99 150
1 100
100 301
2 5
150 250
2
0 720
720 1440

Case #1: CJC
Case #2: IMPOSSIBLE
Case #3: JCCJJ
Case #4: CC

Nguồn

Google Code Jam 2020, Vòng loại, bài Parenting Partnering Returns.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.