这是问题的困难版本。版本之间的区别在于,在这个版本中您需要输出所有需要执行的操作。只有解决了该问题的所有版本,您才能破解。
给你 $$$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$$$ 的运算应用于第三个数组。