CF2059E2.Stop Gaming (Hard Version)

这是该问题的困难版本。两个版本的区别在于此版本需要输出所有需要执行的操作。只有当您解决了该问题的所有版本后才能进行 hack。

给定 $ 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 $（按递增顺序），依次执行以下操作：
  1. 将元素 $ x $ 添加到第 $ k $ 个数组的开头。
  2. 将 $ x $ 赋值为第 $ k $ 个数组的最后一个元素。
  3. 移除第 $ 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 $）——分别表示插入元素的数组索引和元素值。

若存在多个最小操作次数的可行序列，输出其中任意一个即可。

第一个测试用例中，以下 $ 3 $ 次操作的序列是可行的：

1. 对第一个数组应用操作，$ x = 1 $。此时元素 $ 1 $ 被添加到第一个数组开头，$ x $ 的值变为 $ 6 $。移除末尾元素后，第一个数组变为 $ [1, 2] $。接着将 $ x $ 添加到第二个数组开头，$ x $ 的值变为 $ 4 $。移除第二个数组的末尾元素后，两个数组分别变为 $ [1, 2] $ 和 $ [6, 3] $。
2. 对第二个数组应用操作，$ x = 8 $。此时第一个数组保持不变，两个数组分别变为 $ [1, 2] $ 和 $ [8, 6] $。
3. 对第二个数组应用操作，$ x = 7 $，最终两个数组分别达到目标形态 $ [1, 2] $ 和 $ [7, 8] $。

第二个测试用例中，只能通过 $ 5 $ 次操作达成目标数组。

第三个测试用例中，以下 $ 3 $ 次操作的序列是可行的：

1. 对第一个数组应用 $ x = 11 $ 的操作。
2. 对第二个数组应用 $ x = 12 $ 的操作。
3. 对第三个数组应用 $ x = 13 $ 的操作。

翻译由 DeepSeek R1 完成