← 返回题目列表

Codeforces · 1882/E1

E1. 两种排列(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。这两个版本之间的区别在于您不必最小化此版本中的操作数量。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

您有两种排列$$$^{\dagger}$$$ $$$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 \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$$$开始重新索引。
- 对索引为 $$$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$$$。

使用最多 $$$10\,000$$$ 操作找到任何有效的方法来实现目标,或者说不存在。请注意,您不必最小化操作次数。

可以证明,如果可以实现目标,则存在一种最多使用 $$$10\,000$$$ 操作即可实现的方法。

$$$^{\dagger}$$$ 长度 $$$k$$$ 的排列是一个数组,由 $$$k$$$ 不同的整数组成,从 $$$1$$$ 到 $$$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_i \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$$$) —为操作选择的整数。

如果有多个解决方案,请打印其中任何一个。

请注意,您不必最小化操作次数。

示例

输入 #1

3 5
2 1 3
5 2 1 4 3

输出 #1

2
3 4
2 4

输入 #2

4 4
3 4 2 1
2 4 1 3

输出 #2

5
4 2
3 3
1 4
3 2
4 1

输入 #3

2 2
1 2
2 1

输出 #3

-1

注意

在第一个示例中,我们可以在 $$$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]$$$。

在第三个例子中,不可能实现目标。