← 返回题目列表

Codeforces · 180/A

A. 碎片整理

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

在这个问题中,您必须实现一种算法来对硬盘进行碎片整理。硬盘由一系列簇组成,簇的编号为 1 到 n 的整数。磁盘上有m个记录文件,第i个文件占用编号为ai,1,ai,2,...,ai,ni的簇。这些簇不一定连续位于磁盘上,但它们给出的顺序与它们在文件中的顺序相对应(簇 ai, 1 包含第 i 个文件的第一个片段,簇 ai, 2 包含第二个片段,等等)。此外,光盘还必须具有一个或多个没有文件的簇。

允许执行将簇号i的内容复制到簇号j的操作(i和j必须不同)。而且,如果簇号j用来保存一些信息,那么它就会永远丢失。集群没有被清理,但是在碎片整理完成后,其中一些集群被简单地声明为不可用(尽管它们可能仍然包含一些文件碎片)。

您的任务是使用一系列复制操作来确保每个文件占用连续的内存区域。每个文件应占据一个连续的簇部分,文件必须从硬盘的开头一个接一个地排列。碎片整理后,所有空闲(未使用)的簇应该位于硬盘的末尾。碎片整理后的文件可以按任意顺序放置。每个文件的簇应该从第一个到最后一个连续。请参阅注释中的解释性示例。

打印导致磁盘碎片整理的操作序列。请注意,您不必最小化操作次数,但不应超过 2n。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 200) — 相应的簇数和文件数。接下来的 m 行包含文件的描述。该行的第一个数字是ni(ni≥1),即第i个文件占用的簇数。然后遵循 ni 个数字 ai, 1, ai, 2, ..., ai, ni (1 ≤ ai, j ≤ n)。保证每个簇号出现不超过一次且$$\sum_{i=1}^{m} n_i < n$$,即至少存在一个未使用的簇。每行上的数字用空格分隔。

输出

在第一行中打印一个整数 k (0 ≤ k ≤ 2n) — 对磁盘进行碎片整理所需的操作数。接下来的 k 行应包含操作的描述为“i j”(将簇号 i 的内容复制到簇号 j)。

示例

输入 #1

7 2
2 1 2
3 3 4 5

输出 #1

0

输入 #2

7 2
2 1 3
3 2 4 5

输出 #2

3
2 6
3 2
6 3

注意

假设一个磁盘由 8 个簇组成并包含两个文件。第一个文件占用两个簇,第二个文件占用三个簇。让我们看一下碎片整理后文件的正确和错误位置的示例。

$$$$

示例2:每个文件必须占用连续的内存区域。

示例 3:文件之间的顺序并不重要,首先可以写入第二个文件,然后 — 第一个文件。

示例4:不允许破坏文件片段彼此的顺序。

示例5:未使用的簇应位于末尾,在本示例中未使用的簇为3、7、8。