[AdditionalFile5565.zip](file://AdditionalFile5565.zip?type=additional_file)

#5565. 「ROIR 2026 Day1」瘸腿国王

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 ROI Regional 2026 Day1 T2. Хромой король

瘸腿国王在一块 $n \times m$ 的网格棋盘上移动，每次只能走到与当前格子共享边的相邻格子。我们将位于第 $x$ 行第 $y$ 列的格子记作 $(x, y)$。

国王需要访问棋盘上所有格子，每个格子恰好访问一次，并最终返回起始格子（形成一个闭合回路）。棋盘上特别标出了两个相邻的格子：$(x_1, y_1)$ 和 $(x_2, y_2)$。在国王的行走路径中，这两个格子必须连续出现：国王到达其中一个后，必须立即走到另一个。

请找到一条满足条件的行走路径，或者判断这样的路径不存在。

输入格式

第一行两个整数 $n, m$ $(2 \leq n, m \leq 1000)$，表示棋盘的行数和列数。

第二行四个整数 $x_1, y_1, x_2, y_2$ $(1 \leq x_1, x_2 \leq n;\ 1 \leq y_1, y_2 \leq m;\ |x_1 - x_2| + |y_1 - y_2| = 1)$，表示两个必须连续访问的相邻格子。

输出格式

如果不存在满足条件的路径，输出单行 -1。

否则输出 $n \times m + 1$ 对整数，表示路径上依次访问的格子坐标：

• 每对整数为一个格子的行号和列号（用空格分隔）
• 路径必须形成闭合回路，因此起始格子需要在开头和结尾各出现一次
• 路径中 $(x_1, y_1)$ 和 $(x_2, y_2)$ 必须相邻出现（顺序任意）

样例 1

输入

4 3
2 2 3 2

输出

1 1
2 1
2 2
3 2
3 1
4 1
4 2
4 3
3 3
2 3
1 3
1 2
1 1

下图展示了满足条件的行走路径。

样例 2

输入

3 5
1 2 2 2

输出

-1

数据范围与提示

本题共 $50$ 个测试点，每个测试点独立计 $2$ 分。