CF1025E Colored Cubes

Vasya 通过了所有考试！出乎意料的是，Vasya 并不感到疲惫，反而已经准备好迎接新的挑战。然而，他并不想在难题上花费太多精力。 Vasya 想起了自己有一个不太难的谜题：在一个 $n \times n$ 的国际象棋棋盘上，放置着 $m$ 个有颜色的立方体。事实上，$m \leq n$，并且所有立方体的颜色都不同。每个立方体正好占据一个格子。此外，棋盘上为每个立方体都指定了一个目标格子，谜题的目标是将每个立方体移动到它的指定位置。立方体很脆弱，因此每次操作只能将一个立方体移动到它相邻的四个格子之一，并且目标格子必须是空的。Vasya 想要小心操作，因此每次操作恰好需要一秒钟。 Vasya 曾经为 VK Cup 决赛刻苦训练过，所以他最多能专注于这个谜题 $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 \leq k \leq 10800$），表示 Vasya 需要进行的操作次数。 接下来的 $k$ 行，每行描述一次操作，输出四个整数 $x_1$、$y_1$、$x_2$、$y_2$，其中 $(x_1, y_1)$ 表示要移动的立方体当前位置，$(x_2, y_2)$ 表示立方体的新位置。$(x_1, y_1)$ 和 $(x_2, y_2)$ 必须相邻，且 $(x_2, y_2)$ 在操作前必须为空。 保证至少存在一种解。如果有多种方案，输出任意一种即可。

在第四个样例中，所给的移动序列（如下图所示）是合法的，但不是最短的方案。实际上存在只需 $3$ 步的解法。  由 ChatGPT 4.1 翻译