Con tàu Battlestarcraft Algorithmica của chúng ta đang bị những robot dai dẳng mang tên Pylons truy đuổi trong không gian! Chúng ta vừa dịch chuyển tức thời đến một thiên hà mới để cố gắng cắt đuôi chúng. Chúng ta muốn ở lại đây càng lâu càng tốt nhằm có thêm thời gian lên kế hoạch cho bước tiếp theo... nhưng cũng không muốn bị bắt!

Thiên hà này là một lưới phẳng gồm \(R\) hàng và \(C\) cột; các hàng được đánh số từ \(1\) đến \(R\) theo thứ tự từ trên xuống dưới, còn các cột được đánh số từ \(1\) đến \(C\) theo thứ tự từ trái sang phải. Ta có thể chọn ô bắt đầu và phải tiếp tục nhảy giữa các ô cho đến khi đã thăm mỗi ô trong thiên hà đúng một lần. Nói cách khác, ta không bao giờ được thăm lại một ô, kể cả ô bắt đầu.

Ta không muốn khiến Pylons đoán bước đi tiếp theo quá dễ dàng. Mỗi khi nhảy từ ô hiện tại, ta phải chọn một ô đích không cùng hàng, cùng cột hoặc cùng đường chéo với ô hiện tại. Gọi \((i, j)\) là ô ở hàng thứ \(i\) và cột thứ \(j\); một bước nhảy từ ô hiện tại \((r, c)\) đến ô đích \((r', c')\) không hợp lệ khi và chỉ khi ít nhất một trong các điều sau đúng:

• \(r = r'\)
• \(c = c'\)
• \(r - c = r' - c'\)
• \(r + c = r' + c'\)

Bạn có thể giúp chúng ta tìm một thứ tự thăm toàn bộ \(R \times C\) ô sao cho bước đi giữa mọi cặp ô liên tiếp trong dãy đều hợp lệ không? Hay chúng ta không thể thoát khỏi Pylons?

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test gồm một dòng chứa hai số nguyên \(R\) và \(C\): số hàng và số cột của thiên hà này.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó y là một chuỗi chữ cái in hoa, bằng POSSIBLE hoặc IMPOSSIBLE tùy theo việc có thể thỏa mãn các điều kiện trong đề bài hay không. Sau đó, nếu có thể, in thêm \(R \times C\) dòng. Dòng thứ \(i\) trong số này biểu diễn ô thứ \(i\) mà bạn sẽ thăm (đánh số từ \(1\)), và phải chứa hai số nguyên \(r_i\) và \(c_i\): hàng và cột của ô đó. Lưu ý rằng dòng đầu tiên trong số các dòng này biểu diễn ô bắt đầu mà bạn chọn.

Ràng buộc

Phân nhóm

Test Set 1 (Hiển thị):

• \(T = 16\).
• \(2 \le R \le 5\).
• \(2 \le C \le 5\).

Test Set 2 (Ẩn):

• \(1 \le T \le 100\).
• \(2 \le R \le 20\).
• \(2 \le C \le 20\).

Đ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ụ

2
2 2
2 5

Case #1: IMPOSSIBLE
Case #2: POSSIBLE
2 3
1 1
2 4
1 2
2 5
1 3
2 1
1 5
2 2
1 4

Nguồn

Google Code Jam 2019, Vòng 1A, bài Pylons.

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