CF1882E2 Two Permutations (Hard Version)

这是该问题的困难版本。两个版本的区别在于本版本需要你最小化操作次数。只有当你同时解决了两个版本的问题时，才能进行 hack。 你有两个排列 $p_1, p_2, \ldots, p_n$（由 $1$ 到 $n$ 的整数组成）和 $q_1, q_2, \ldots, q_m$（由 $1$ 到 $m$ 的整数组成）。初始时 $p_i = a_i$，其中 $i=1,2,\ldots,n$，$q_j = b_j$，其中 $j=1,2,\ldots,m$。你可以对这两个排列进行若干次（可能为零次）如下操作。 每次操作，$p$ 和 $q$ 会按照以下三个步骤发生变化： - 你选择整数 $i$ 和 $j$，满足 $1 \le i \le n$ 且 $1 \le j \le m$。 - 将排列 $p$ 以 $p_i$ 为轴分为三部分：左部分为 $p_1, p_2, \ldots, p_{i-1}$（可能为空），中间部分为单个元素 $p_i$，右部分为 $p_{i+1}, p_{i+2}, \ldots, p_n$（可能为空）。接下来，将左部分和右部分交换。形式化地说，操作后 $p$ 变为 $p_{i+1}, p_{i+2}, \ldots, p_n, p_i, p_1, p_2, \ldots, p_{i-1}$。新排列重新从 $1$ 开始编号。 - 对 $q$ 也进行同样的操作，选定下标 $j$。形式化地说，操作后 $q$ 变为 $q_{j+1}, q_{j+2}, \ldots, q_m, q_j, q_1, q_2, \ldots, q_{j-1}$。新排列重新从 $1$ 开始编号。 你的目标是同时让 $p_i = i$ 对于所有 $i=1,2,\ldots,n$，且 $q_j = j$ 对于所有 $j=1,2,\ldots,m$。 请找出一种用最少操作次数达成目标的方法，或者说明无解。请注意，你需要最小化操作次数。 一个长度为 $k$ 的排列是由 $1$ 到 $k$ 的 $k$ 个互不相同的整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 出现了两次），$[1,3,4]$ 也不是排列（$k=3$ 但数组中有 $4$）。

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2500$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）。 第三行包含 $m$ 个整数 $b_1, b_2, \ldots, b_m$（$1 \le b_j \le m$）。 保证 $a$ 和 $b$ 都是排列。

如果无解，输出一个整数 $-1$。 否则，输出一个整数 $k$，表示需要操作的次数，接下来 $k$ 行，每行两个整数 $i$ 和 $j$（$1 \le i \le n$，$1 \le j \le m$），表示每次操作选择的下标。 如果有多种方案，输出任意一种。 请注意，你需要最小化操作次数。

在第一个测试用例中，我们可以在 $2$ 次操作内达成目标： 1. 第一次操作选择 $i=3$，$j=4$。操作后 $p$ 变为 $[3,2,1]$，$q$ 变为 $[3,4,5,2,1]$。 2. 第二次操作选择 $i=2$，$j=4$。操作后 $p$ 变为 $[1,2,3]$，$q$ 变为 $[1,2,3,4,5]$。 在第三个测试用例中，不可能达成目标。 由 ChatGPT 4.1 翻译