310760: CF1882E2. Two Permutations (Hard Version)

E2. Two Permutations (Hard Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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).

Input

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.

Output

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.

ExamplesInput

3 5
2 1 3
5 2 1 4 3

Output

2
3 4
2 4

Input

4 4
3 4 2 1
2 4 1 3

Output

3
3 3
1 4
4 2

Input

2 2
1 2
2 1

Output

-1

Note

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.

题目大意：

这是一个难题的较难版本。两个版本之间的区别在于，在这个版本中，你需要最小化操作的数量。只有当问题的两个版本都被解决时，你才能进行攻击。

你有两个排列 $ 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 将根据以下三个步骤进行更改：

1. 你选择满足 $ 1 \le i \le n $ 和 $ 1 \le j \le m $ 的整数 $ i $、$ j $。
2. 使用 $ p_i $ 作为枢轴将排列 p 分为三个部分：左部分由元素 $ 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 开始重新索引。
3. 使用索引 j 对 q 执行相同的转换。形式上，在此步骤之后，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 $。

找到使用可能的最小操作数实现目标的任何方法，或者说明不存在这样的方法。请注意，你**必须**最小化操作的数量。

输入输出数据格式：

输入：

- 第一行包含两个整数 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 是排列。

输出：

- 如果没有解决方案，则打印单个整数 -1。
- 否则，打印一个整数 k —— 要执行的操作数，后跟 k 行，每行包含两个整数 i 和 j ($ 1 \le i \le n $, $ 1 \le j \le m $) —— 操作中选择的整数。
- 如果有多个解决方案，则打印其中任何一个。
- 请注意，你**必须**最小化操作的数量。

示例：

输入：
```
3 5
2 1 3
5 2 1 4 3
```
输出：
```
2
3 4
2 4
```

输入：
```
4 4
3 4 2 1
2 4 1 3
```
输出：
```
3
3 3
1 4
4 2
```

输入：
```
2 2
1 2
2 1
```
输出：
```
-1
```题目大意： 这是一个难题的较难版本。两个版本之间的区别在于，在这个版本中，你需要最小化操作的数量。只有当问题的两个版本都被解决时，你才能进行攻击。 你有两个排列 $ 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 将根据以下三个步骤进行更改： 1. 你选择满足 $ 1 \le i \le n $ 和 $ 1 \le j \le m $ 的整数 $ i $、$ j $。 2. 使用 $ p_i $ 作为枢轴将排列 p 分为三个部分：左部分由元素 $ 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 开始重新索引。 3. 使用索引 j 对 q 执行相同的转换。形式上，在此步骤之后，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 $。 找到使用可能的最小操作数实现目标的任何方法，或者说明不存在这样的方法。请注意，你**必须**最小化操作的数量。 输入输出数据格式： 输入： - 第一行包含两个整数 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 是排列。 输出： - 如果没有解决方案，则打印单个整数 -1。 - 否则，打印一个整数 k —— 要执行的操作数，后跟 k 行，每行包含两个整数 i 和 j ($ 1 \le i \le n $, $ 1 \le j \le m $) —— 操作中选择的整数。 - 如果有多个解决方案，则打印其中任何一个。 - 请注意，你**必须**最小化操作的数量。 示例： 输入： ``` 3 5 2 1 3 5 2 1 4 3 ``` 输出： ``` 2 3 4 2 4 ``` 输入： ``` 4 4 3 4 2 1 2 4 1 3 ``` 输出： ``` 3 3 3 1 4 4 2 ``` 输入： ``` 2 2 1 2 2 1 ``` 输出： ``` -1 ```