← 返回题目列表

Codeforces · 2192/E

E. 交换以重新排列

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

给定 $$$2$$$ 数组,$$$a$$$ 和 $$$b$$$,长度均为 $$$n$$$。您可以执行以下操作:

  • 选择一个索引 $$$i$$$ ($$$1 \le i \le n$$$) 并将 $$$a_i$$$ 与 $$$b_i$$$ 交换。

您可以执行该操作任意次数(可能为零),但每个索引可以通过以下方式选择 最多 1 个 操作。你的任务是在所有操作之后使$$$a$$$重新排列$$$b$$$,或者声明这是不可能的。您不必最小化操作次数。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$)。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \leq b_i \leq n$$$)。

保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,如果不可能使 $$$a$$$ 重新排列 $$$b$$$,则输出 $$$-1$$$。否则,按以下格式输出两行:

  • 在第一行中,打印操作数 $$$s$$$ ($$$0 \leq s \leq n$$$)。
  • 在每个测试用例的第二行中,打印 $$$s$$$ 数字 – 您在每个操作中按顺序选择的索引。您应该保证每个索引最多被选择一次。

如果有多个可能的答案,您可以输出任何一个。

示例

输入
复制

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

输出
复制

2
2 4
-1
0

2
3 4

注意

在第一个测试用例中,执行的操作是 swap($$$a_2, b_2$$$) 和 swap($$$a_4,b_4$$$),这将使 $$$a = [1,2,3,4]$$$ 和 $$$b = [2,1,4,3]$$$。现在可以通过重新排列$$$b$$$的元素来实现$$$a$$$。

在第二个测试用例中,可以证明,无论我们做什么操作,我们都不能让$$$a$$$重新排列$$$b$$$。