CF1882E2.Two Permutations (Hard Version)

This is the hard version of the problem. The difference between the two versions is that you have to minimize the number of operations in this version. You can make hacks only if both versions of the problem are solved.

You have two permutations$^{\dagger}$ $p_{1}, p_{2}, \ldots, p_{n}$ (of integers $1$ to $n$) and $q_{1}, q_{2}, \ldots, q_{m}$ (of integers $1$ to $m$). Initially $p_{i}=a_{i}$ for $i=1, 2, \ldots, n$, and $q_{j} = b_{j}$ for $j = 1, 2, \ldots, m$. You can apply the following operation on the permutations several (possibly, zero) times.

In one operation, $p$ and $q$ will change according to the following three steps:

• You choose integers $i$, $j$ which satisfy $1 \le i \le n$ and $1 \le j \le m$.
• Permutation $p$ is partitioned into three parts using $p_i$ as a pivot: the left part is formed by elements $p_1, p_2, \ldots, p_{i-1}$ (this part may be empty), the middle part is the single element $p_i$, and the right part is $p_{i+1}, p_{i+2}, \ldots, p_n$ (this part may be empty). To proceed, swap the left and the right parts of this partition. Formally, after this step, $p$ will become $p_{i+1}, p_{i+2}, \ldots, p_{n}, p_{i}, p_{1}, p_{2}, \ldots, p_{i-1}$. The elements of the newly formed $p$ will be reindexed starting from $1$.
• Perform the same transformation on $q$ with index $j$. Formally, after this step, $q$ will become $q_{j+1}, q_{j+2}, \ldots, q_{m}, q_{j}, q_{1}, q_{2}, \ldots, q_{j-1}$. The elements of the newly formed $q$ will be reindexed starting from $1$.

Your goal is to simultaneously make $p_{i}=i$ for $i=1, 2, \ldots, n$, and $q_{j} = j$ for $j = 1, 2, \ldots, m$.

Find any way to achieve the goal using the minimum number of operations possible, or say that none exists. Please note that you have to minimize the number of operations.

$^{\dagger}$ A permutation of length $k$ is an array consisting of $k$ distinct integers from $1$ to $k$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($k=3$ but there is $4$ in the array).

这是该问题的困难版本。两个版本的区别在于：在本版本中，你必须最小化操作次数。仅当两个版本的问题均被解决时，你才可以进行 hack。

你有两个排列$^{\dagger}$：$p_{1}, p_{2}, \ldots, p_{n}$（由整数 $1$ 到 $n$ 构成）和 $q_{1}, q_{2}, \ldots, q_{m}$（由整数 $1$ 到 $m$ 构成）。初始时，对 $i=1, 2, \ldots, n$，有 $p_{i}=a_{i}$；对 $j = 1, 2, \ldots, m$，有 $q_{j} = b_{j}$。你可以对这两个排列执行若干次（可能为零次）如下操作。

每次操作包含以下三个步骤：

• 你选择满足 $1 \le i \le n$ 和 $1 \le j \le m$ 的整数 $i$ 和 $j$。
• 将排列 $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}$。新形成的 $p$ 的元素将从下标 $1$ 开始重新编号。
• 对 $q$ 在索引 $j$ 处执行完全相同的变换。形式上，此步骤后，$q$ 变为 $q_{j+1}, q_{j+2}, \ldots, q_{m}, q_{j}, q_{1}, q_{2}, \ldots, q_{j-1}$。新形成的 $q$ 的元素将从下标 $1$ 开始重新编号。

你的目标是同时使 $p_{i}=i$ 对所有 $i=1, 2, \ldots, n$ 成立，且 $q_{j} = j$ 对所有 $j = 1, 2, \ldots, m$ 成立。

请找出一种使用最少操作次数达成目标的方法，或判定不存在可行方案。请注意，你必须最小化操作次数。

$^{\dagger}$ 长度为 $k$ 的排列是指由 $1$ 到 $k$ 中 $k$ 个互不相同的整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（此时 $k=3$，但数组中包含了 $4$）。

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2500$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).

The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($1 \le b_i \le m$).

It is guaranteed that $a$ and $b$ are permutations.

第一行包含两个整数 $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_i \le m$）。

保证 $a$ 和 $b$ 均为排列。

If there is no solution, print a single integer $-1$.

Otherwise, print an integer $k$ — the number of operations to perform, followed by $k$ lines, each containing two integers $i$ and $j$ ($1 \le i \le n$, $1 \le j \le m$) — the integers chosen for the operation.

If there are multiple solutions, print any of them.

Please note that you have to minimize the number of operations.

如果无解，请输出单个整数 $-1$。

否则，先输出一个整数 $k$ —— 表示需要执行的操作次数，随后输出 $k$ 行，每行包含两个整数 $i$ 和 $j$（$1 \le i \le n$，$1 \le j \le m$）—— 表示该操作所选择的整数。

若存在多个解，输出任意一个即可。

请注意，你必须使操作次数最小化。

In the first test case, we can achieve the goal within $2$ operations:

1. In the first operation, choose $i = 3$, $j = 4$. After this, $p$ becomes $[3, 2, 1]$ and $q$ becomes $[3, 4, 5, 2, 1]$.
2. In the second operation, choose $i = 2$, $j = 4$. After this, $p$ becomes $[1, 2, 3]$ and $q$ becomes $[1, 2, 3, 4, 5]$.

In the third test case, it is impossible to achieve the goal.

在第一个测试用例中，我们可以在 $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]$。

在第三个测试用例中，无法达成目标。