← 返回题目列表

Codeforces · 111/E

E. Petya 和矩形

中文机器翻译题面 查看原题

小 Petya 喜欢玩矩形。妈妈给 Petya 买了一个矩形,分为 n × m 大小的单元格(包含 n 行,m 列)。 Petya 标记了矩形的两个不同单元格,现在他正在解决以下任务:

让我们将这两个单元之间的简单路径定义为不同单元 a1、a2、...、ak 的序列,其中 a1 和 ak 是两个标记的单元。此外,ai 和ai + 1 是路径的旁边相邻单元(1 ≤ i < k)。我们将路径长度表示为数字 k(序列长度)。

Petya 的任务是找到最长的简单路径的长度并打印该路径。帮助他。

输入

第一行包含空格分隔的整数 n 和 m (4 ≤ n, m ≤ 1000) — 相应地,矩形中的行数和列数。第二行包含空格分隔的整数 x1 和 y1 — 第一个标记单元的坐标。第三行包含空格分隔的整数 x2 y2 — 第二个标记单元的坐标 (1 < x1, x2 < n, 1 < y1, y2 < m, x1 ≠ x2, y1 ≠ y2)。

标记单元格的坐标是一对整数 x y,其中 x 表示行号,y 表示列号。行从上到下使用从 1 到 n 的连续整数进行编号。这些列从左到右用 1 到 m 的连续整数进行编号。

保证标记的单元格不位于一行或一列中。

输出

在第一行中打印找到的路径的长度 — k。在接下来的行中,打印 k 对整数,每行一个 - 构成所找到路径的单元格的坐标,按顺序排列,它们在路径中遵循这些顺序(路径必须从单元格 (x1, y1) 到单元格 (x2, y2))。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

4 4
2 2
3 3

输出 #1

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

注意

语句测试如图所示: