Bạn là Người làm vườn thành Seville, một nhân vật phụ trong một vở opera. Bối cảnh là một sân hình chữ nhật gồm các ô vuông đơn vị, có \(R\) hàng và \(C\) cột. Bạn được yêu cầu dựng một mê cung hàng rào: mỗi ô phải chứa một hàng rào chạy chéo từ góc này sang góc đối diện. Có hai loại hàng rào: từ góc dưới trái đến góc trên phải, ký hiệu /, và từ góc trên trái đến góc dưới phải, ký hiệu \. Khi hai hàng rào chạm nhau, chúng tạo thành một bức tường liên tục.

Bao quanh sân là một vành ngoài gồm các ô đơn vị rộng một ô, bỏ đi bốn ô ở góc. Mỗi ô ngoài là nơi ở của một cận thần. Các cận thần được đánh số theo chiều kim đồng hồ: bắt đầu bằng 1 ở ô ngoài cùng bên trái của hàng trên, và kết thúc bằng \(2(R+C)\) ở ô trên cùng của cột bên trái. Chẳng hạn, với \(R=2\), \(C=2\), khi chưa dựng hàng rào, cách đánh số là:

 12
8  3
7  4
 65

Trong vở opera kỳ lạ này, tình yêu vừa có qua có lại vừa độc quyền: mỗi cận thần yêu đúng một người khác, và người đó cũng chỉ yêu lại họ. Mỗi người muốn lẻn qua mê cung đến chỗ người yêu mà không gặp bất kỳ cận thần nào khác. Nói cách khác, mỗi cặp yêu nhau phải được nối bằng một lối đi qua mê cung, và lối ấy phải được các bức tường hàng rào ngăn cách với mọi lối khác. Một số phần của mê cung không thuộc lối đi của ai cũng không sao, miễn là mọi cặp người yêu đều được nối.

Cho danh sách các cặp yêu nhau, hãy dựng mê cung hàng rào thỏa mãn yêu cầu, hoặc xác định rằng điều đó là IMPOSSIBLE.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa hai số nguyên \(R\) và \(C\), sau đó là một dòng chứa một hoán vị của toàn bộ các số nguyên từ 1 đến \(2(R+C)\). Mỗi số là chỉ số một cận thần; phần tử thứ nhất và thứ hai trong danh sách là một cặp cần nối, phần tử thứ ba và thứ tư là một cặp, và cứ tiếp tục như vậy.

Dữ liệu ra

Với mỗi bộ test, trước tiên in một dòng chỉ chứa Case #x:, trong đó x là số thứ tự bộ test, bắt đầu từ 1. Nếu không thể thỏa mãn các điều kiện, in thêm một dòng IMPOSSIBLE. Nếu có thể, in thêm \(R\) dòng, mỗi dòng gồm đúng \(C\) ký tự biểu diễn mê cung; mỗi ký tự phải là / hoặc \, không được để trống ô nào. Nếu có nhiều mê cung hợp lệ, có thể in bất kỳ một mê cung nào.

Ràng buộc

Phân nhóm

Test Set 1 (Small, hiển thị)

• \(1\le T\le100\).
• \(1\le R\times C\le16\).

Test Set 2 (Large, ẩn)

• \(1\le T\le500\).
• \(1\le R\times C\le100\).

Đ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
1 1
1 4 3 2
1 3
1 8 2 7 3 4 5 6
2 2
8 1 4 5 2 3 7 6
1 1
1 3 2 4

Case #1:
/
Case #2:
//\
Case #3:
//
\/
Case #4:
IMPOSSIBLE

/\
\/

Nguồn

Google Code Jam 2016, Vòng 2, bài The Gardener of Seville.

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