← 返回题目列表

Codeforces · 1025/E

E. 彩色立方体

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

Vasya 通过了所有考试!尽管充满期待,瓦夏并不疲倦,而且他已经准备好迎接新的挑战。然而,他不想在困难的问题上付出太多的努力。

Vasya 记得他有一个不那么难的谜题:$$$m$$$ 彩色立方体被放置在大小为 $$$n \times n$$$ 的棋盘上。事实是 $$$m \leq n$$$ 和所有立方体都有不同的颜色。每个立方体恰好占据一个单元格。此外,棋盘上的每个立方体都有一个指定的单元格,谜题是将每个立方体放置在其位置上。立方体是易碎的,因此在一项操作中,您只能将一个立方体移动到四个相邻的旁边单元格之一上,前提是该单元格是空的。 Vasya 想要小心谨慎,因此每次操作只需要一秒钟。

Vasya曾经为了VK杯决赛而刻苦训练,所以他最多可以将注意力集中在拼图上$$$3$$$小时,即$$$10800$$$秒。帮助 Vasya 找到这样的操作顺序,使所有立方体都将被移动到指定的位置,而 Vasya 不会失去他的注意力。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq m \leq n \leq 50$$$)。

接下来的 $$$m$$$ 行包含两个整数 $$$x_i$$$, $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$),即立方体的初始位置。

接下来的 $$$m$$$ 行以相同的格式和顺序描述了立方体的指定位置。

保证所有初始位置都是不同的并且所有指定位置都是不同的,但是,有可能一些初始位置与一些最终位置重合。

输出

在第一行打印一个整数 $$$k$$$ ($$$0 \le k \leq 10800$$$) — Vasya 应该进行的操作数。

在接下来的 $$$k$$$ 行中,您应该描述一个操作:打印四个整数 $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$,其中 $$$x_1, y_1$$$ 是 Vasya 应该移动的立方体的位置,$$$x_2, y_2$$$ 是立方体的新位置。单元格 $$$x_1, y_1$$$ 和 $$$x_2, y_2$$$ 应有公共边,单元格 $$$x_2, y_2$$$ 在操作前应为空。

我们可以证明总是存在至少一个解决方案。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

2 1
1 1
2 2

输出 #1

2
1 1 1 2
1 2 2 2

输入 #2

2 2
1 1
2 2
1 2
2 1

输出 #2

2
2 2 2 1
1 1 1 2

输入 #3

2 2
2 1
2 2
2 2
2 1

输出 #3

4
2 1 1 1
2 2 2 1
1 1 1 2
1 2 2 2

输入#4

4 3
2 2
2 3
3 3
3 2
2 2
2 3

输出#4

9
2 2 1 2
1 2 1 1
2 3 2 2
3 3 2 3
2 2 1 2
1 1 2 1
2 1 3 1
3 1 3 2
1 2 2 2

注意

在第四个示例中,打印的运动序列(如下图所示)有效,但不是最短的。 $$$3$$$操作中有一个解决方案。