← 返回题目列表

Codeforces · 2084/C

C. 你优雅翱翔远方

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

给你一个排列 $$$a$$$ 和 $$$b$$$,长度为 $$$n$$$$$$^{\text{*}}$$$。您最多可以执行$$$n$$$次以下操作:

  • 选择两个索引 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i \ne j$$$),将 $$$a_i$$$ 与 $$$a_j$$$ 交换,将 $$$b_i$$$ 与 $$$b_j$$$ 交换。

判断$$$a$$$和$$$b$$$运算后是否可以互相颠倒。换句话说,对于每个 $$$i = 1, 2, \ldots, n$$$, $$$a_i = b_{n + 1 - i}$$$。

如果可能,输出任何有效的操作序列。否则,输出$$$-1$$$。

$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 排列的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$)。

保证 $$$a$$$ 和 $$$b$$$ 是长度 $$$n$$$ 的排列。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,如果不可能,则在唯一的行中输出$$$-1$$$。否则,输出单个整数 $$$m$$$ ($$$0 \le m \le n$$$) — 第一行中的操作数。在接下来的 $$$m$$$ 行中,按顺序输出每个操作中的索引 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i \ne j$$$)。如果有多个解决方案,请打印其中任何一个。

示例

输入
复制

5
2
1 2
1 2
2
1 2
2 1
4
1 3 2 4
2 4 1 3
5
2 5 1 3 4
3 5 4 2 1
5
3 1 2 4 5
1 2 3 4 5

输出
复制

-1
0
1
1 2
2
1 2
1 3
-1

注意

在第二个测试用例中,$$$b$$$ 已经是 $$$a$$$ 的反转。

在第三个测试用例中,执行以下操作后,$$$b$$$将变为$$$a$$$的反转:

  • 交换 $$$a_1, a_2$$$ 并交换 $$$b_1, b_2$$$。现在 $$$a = [3, 1, 2, 4]$$$ 和 $$$b = [4, 2, 1, 3]$$$。

在第四个测试用例中,按顺序执行以下操作后,$$$b$$$将变为$$$a$$$的反转:

  • 交换 $$$a_1, a_2$$$ 并交换 $$$b_1, b_2$$$。现在 $$$a = [5, 2, 1, 3, 4]$$$ 和 $$$b = [5, 3, 4, 2, 1]$$$。
  • 交换 $$$a_1, a_3$$$ 并交换 $$$b_1, b_3$$$。现在 $$$a = [1, 2, 5, 3, 4]$$$ 和 $$$b = [4, 3, 5, 2, 1]$$$。