← 返回题目列表

Codeforces · 1385/G

G. 列交换

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

给您一个表 $$$a$$$,大小为 $$$2 \times n$$$(即两行和 $$$n$$$ 列),由从 $$$1$$$ 到 $$$n$$$ 的整数组成。

一步操作中,您可以选择某列 $$$j$$$ ($$$1 \le j \le n$$$) 并交换其中的值 $$$a_{1, j}$$$ 和 $$$a_{2, j}$$$。每列只能选择一次。

您的任务是找到在表的第一行和第二行中获得大小为 $$$n$$$ 的排列所需的最小移动次数,或者确定是否不可能做到这一点。

您必须回答 $$$t$$$ 独立测试用例。

回想一下,$$$n$$$ 大小的排列是这样一个大小为 $$$n$$$ 的数组,其中包含从 $$$1$$$ 到 $$$n$$$ 的每个整数恰好一次(元素的顺序无关紧要)。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 表中的列数。测试用例的第二行包含 $$$n$$$ 整数 $$$a_{1, 1}, a_{1, 2}, \dots, a_{1, n}$$$ ($$$1 \le a_{1, i} \le n$$$),其中 $$$a_{1, i}$$$ 是表第一行的第 $$$i$$$ 个元素。测试用例的第三行包含 $$$n$$$ 整数 $$$a_{2, 1}, a_{2, 2}, \dots, a_{2, n}$$$ ($$$1 \le a_{2, i} \le n$$$),其中 $$$a_{2, i}$$$ 是表第二行的第 $$$i$$$ 个元素。

保证$$$n$$$之和不超过$$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$)。

输出

对于每个测试用例,打印答案: -1 如果不可能在表的第一行和第二行中获得大小 $$$n$$$ 的排列,或者在第一行中获得一个整数 $$$k$$$,其中 $$$k$$$ 是在两行中获得排列所需的最小移动次数,并且 $$$k$$$ 不同的整数 $$$pos_1, pos_2, \dots,第二行中的 pos_k$$$ ($$$1 \le pos_i \le n$$$) 以任意顺序 — 需要交换值以获得两行排列的列索引。如果有多个答案,您可以打印任何一个。

示例

输入 #1

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

输出 #1

0

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