CF1882E1 Two Permutations (Easy 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$ 以 $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$。 请找出一种在不超过 $10\,000$ 次操作内达成目标的方案，或者说明无解。注意，你不需要最小化操作次数。 可以证明，如果存在可行解，则一定存在不超过 $10\,000$ 次操作的方案。 排列的定义：长度为 $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$（$0 \le k \le 10\,000$），表示操作次数。接下来 $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 翻译