← 返回题目列表

Codeforces · 2059/E2

E2. 停止游戏(硬版)

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

这是问题的困难版本。版本之间的区别在于,在这个版本中您需要输出所有需要执行的操作。只有解决了该问题的所有版本,您才能破解。

给你 $$$n$$$ 个数组,每个数组的长度为 $$$m$$$。令第 $$$i$$$ 数组的第 $$$j$$$ 个元素表示为 $$$a_{i, j}$$$。保证所有 $$$a_{i, j}$$$ 成对不同。在一项操作中,您可以执行以下操作:

- 选择一些整数 $$$i$$$ ($$$1 \le i \le n$$$) 和一个整数 $$$x$$$ ($$$1 \le x \le 2 \cdot n \cdot m$$$)。
- 对于从 $$$i$$$ 到 $$$n$$$ 按升序排列的所有整数 $$$k$$$,执行以下操作: 将元素 $$$x$$$ 添加到第 $$$k$$$ 数组的开头。 将第 $$$k$$$ 数组中最后一个元素的值分配给 $$$x$$$。 从第 $$$k$$$ 数组中删除最后一个元素。

换句话说,您可以在任何数组的开头插入一个元素,之后该数组以及所有后续数组中的所有元素都会向右移动一位。最后一个数组的最后一个元素被删除。

还为您提供了所有操作后需要获取的数组的描述。也就是说,执行操作后,第 $$$i$$$ 数组的第 $$$j$$$ 元素应等于 $$$b_{i, j}$$$。保证所有 $$$b_{i, j}$$$ 成对不同。

确定获得所需数组所需执行的最少操作数,并输出所有操作本身的顺序。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$) - 数组的数量和每个数组中元素的数量。

以下 $$$n$$$ 行中的第 $$$i$$$ 包含 $$$m$$$ 整数 $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ ($$$1 \le a_{i, j} \le 2 \cdot n \cdot m$$$) —第 $$$i$$$ 个原始数组。保证所有 $$$a_{i, j}$$$ 成对不同。

以下 $$$n$$$ 行中的第 $$$i$$$ 包含 $$$m$$$ 整数 $$$b_{i, 1}, b_{i, 2}, \ldots, b_{i, m}$$$ ($$$1 \le b_{i, j} \le 2 \cdot n \cdot m$$$) —第 $$$i$$$ 个最终数组。保证所有 $$$b_{i, j}$$$ 成对不同。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 需要执行的最少操作数。

接下来,每个操作输出两个整数 $$$i$$$ 和 $$$x$$$ ($$$1 \le i \le n$$$, $$$1 \le x \le 2 \cdot n \cdot m$$$) — 分别是插入元素的数组的索引和元素的值。

如果存在多个具有最少操作数的可能序列,则输出其中任何一个。

示例

输入 #1

4
2 2
2 6
3 4
1 2
7 8
1 5
5 4 1 2 3
5 4 3 2 1
3 3
1 2 3
4 5 6
7 8 9
11 1 2
12 3 4
13 5 6
4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 1 2 3
4 18 5 6
7 19 8 20
9 21 22 10

输出 #1

3
1 1
2 8
2 7
5
1 1
1 2
1 3
1 4
1 5
3
1 11
2 12
3 13
6
3 20
2 18
3 19
4 22
4 21
1 17

注意

在第一个测试用例中,以下 $$$3$$$ 操作序列是合适的:

- 将操作应用于 $$$x = 1$$$ 的第一个数组。然后元素$$$1$$$将被添加到第一个数组的开头,$$$x$$$的值将变为$$$6$$$。最后一个元素将被删除,第一个数组将类似于 $$$[1, 2]$$$。接下来,将元素 $$$x$$$ 添加到第二个数组的开头,$$$x$$$ 的值变为 $$$4$$$。第二个数组的最后一个元素被删除,第一次操作后,两个数组分别看起来像 $$$[1, 2]$$$ 和 $$$[6, 3]$$$。
- 将运算应用于 $$$x = 8$$$ 的第二个数组。那么第一个数组保持不变,两个数组将分别看起来像 $$$[1, 2]$$$ 和 $$$[8, 6]$$$。
- 将操作应用于 $$$x = 7$$$ 的第二个数组,然后两个数组将分别具有所需的外观 $$$[1, 2]$$$ 和 $$$[7, 8]$$$。

在第二个测试用例中,所需的数组只能通过 $$$5$$$ 操作来实现。

在第三个测试用例中,以下 $$$3$$$ 操作序列是合适的:

- 将 $$$x = 11$$$ 的运算应用于第一个数组。
- 将 $$$x = 12$$$ 的运算应用于第二个数组。
- 将 $$$x = 13$$$ 的运算应用于第三个数组。