Description

我们的 Battlestarcraft Algorithmica 飞船正在太空中被名为 Pylons 的顽固机器人追赶！我们刚刚传送到一个新的星系，试图甩掉它们，并希望能在这里停留尽可能长的时间，以便为下一步行动争取时间……但我们绝不能被抓住！

这个星系是一个 $R$ 行 $C$ 列的平面网格；行从上到下编号为 $1$ 到 $R$，列从左到右编号为 $1$ 到 $C$。我们可以选择从任意一个格子开始，并且必须不断地跳跃到其他格子，直到每个格子都恰好访问一次。也就是说，我们不能重复访问任何格子，包括起始格子。

我们不希望让 Pylons 太容易猜到我们下一步会去哪里。每次从当前格子跳跃时，必须选择一个不与当前格子在同一行、同一列或同一对角线上的目标格子。设 $(i, j)$ 表示第 $i$ 行第 $j$ 列的格子；那么从当前格子 $(r, c)$ 跳到目标格子 $(r', c')$ 是无效的，当且仅当以下任一条件成立：

• $r = r'$
• $c = c'$
• $r - c = r' - c'$
• $r + c = r' + c'$

你能帮我们找到一种访问 $R \times C$ 个格子的顺序，使得任意一对相邻格子的移动都是有效的吗？或者说，我们根本无法逃脱 Pylons 的追捕？

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 个测试用例。每个测试用例包含一行，包含两个整数 $R$ 和 $C$，分别表示这个星系的行数和列数。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $y$ 是一个大写字母字符串：如果可以满足题目要求则为 POSSIBLE，否则为 IMPOSSIBLE。如果可能，请接着输出 $R \times C$ 行，第 $i$ 行表示你访问的第 $i$ 个格子（从 $1$ 开始计数），包含两个整数 $r_i$ 和 $c_i$，分别表示该格子的行号和列号。注意，第一行表示你选择的起始格子。

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

Hint

样例解释

在样例第 1 组中，无论选择哪个起始格子，都无法跳到其他格子，因为剩下的所有格子都与起始格子在同一行、同一列或同一对角线上。

在样例第 2 组中，我们选择了第 2 行第 3 列的格子作为起始格子。注意，最后一个格子可以与起始格子在同一行、同一列或同一对角线上。下图展示了访问格子的顺序：

2 4 6 10 8
7 9 1 3  5

数据范围

测试点 1（8 分，可见）

• $\text{T} = 16$
• $2 \leqslant \text{R} \leqslant 5$
• $2 \leqslant \text{C} \leqslant 5$

测试点 2（23 分，隐藏）

• $1 \leqslant \text{T} \leqslant 100$
• $2 \leqslant \text{R} \leqslant 20$
• $2 \leqslant \text{C} \leqslant 20$

由 ChatGPT 4.1 翻译