← 返回题目列表

Codeforces · 1250/M

M. 智能花园

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

Berland Gardeners United Inc. 雇用您参与名为“SmartGarden”的项目。该项目的主要特点是自动花园浇水。

正式地,花园可以表示为 $$$n \times n$$$ 个单元格的正方形,其中从上到下编号为 $$$1$$$ 到 $$$n$$$ 的行,从左到右编号为 $$$1$$$ 到 $$$n$$$ 的列。花园的每个单元格都包含一株植物或一块平板。

众所周知,板位于代表花园的矩阵的主对角线上,以及位于主对角线下方并与主对角线的至少一个单元共享一侧的单元中。花园里所有剩余的房间都种满了植物。

$$$n=5$$$ 的花园示例。

在项目实施过程中,您创建了一个智能机器人,它将一系列命令作为输入,并逐一进行处理。每个命令包含:

- 水平线列表(矩阵中代表花园的行);
- 垂直线列表(矩阵中代表花园的列)。

执行每个命令时,机器人仅浇灌指定行和指定列交叉处的单元格。因此,如果您指定 $$$r$$$ 行和 $$$c$$$ 列,那么 $$$r \cdot c$$$ 单元格将被浇水。

在为客户提供的演示中,您已经调整了机器人,使其可以浇灌整个花园。为此,您准备了一个包含所有 $$$n$$$ 行和所有 $$$n$$$ 列的命令。

不幸的是,在为您的客户进行演示前 5 小时,Berland Gardeners United Inc. 的首席执行官将参加演示。此外,在演示期间他很可能会站在花园的石板上!

现在您需要为机器人创建一个命令列表,以便它给所有植物浇水,并且不给任何包含平板的单元格浇水。由于它只是“SmartGarden”的测试版,因此命令总数不应超过$$$50$$$。

创建一个程序,对于给定大小的花园,将找到不超过 $$$50$$$ 命令的列表,这些命令允许机器人给花园中的所有植物浇水,而无需浇水板。允许给植物浇水多次。

输入

输入的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5000$$$),其中 $$$n$$$ 是花园的大小。

输出

在第一行中打印机器人 $$$k$$$ 的命令总数 ($$$1 \le k \le 50$$$)。在接下来的 $$$2 \cdot k$$$ 行中打印所有命令。每个命令应由 $$$2$$$ 行指定。每个命令的第一行应描述命令中的行,第二行应描述命令中的列。这些 $$$2$$$ 行中的每一行都应具有以下格式:

- 行的第一个数字应指定相应列表中的项目总数 $$$x$$$ ;
- 然后是 $$$x$$$ 不同的数字,其中每个数字都在 $$$1 \dots n$$$ 范围内,并描述第一行的选定行和第二行的选定列。

如果有多种浇灌花园的方法,请打印其中任何一种。

示例

输入 #1

2

输出 #1

2
1 1
1 2
1 1
1 2

输入 #2

4

输出 #2

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