← 返回题目
题库练习 Swap to Rearrange
← 上一题 下一题 →

A16722 | Swap to Rearrange

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

给定两个长度为 $n$ 的数组 $a$ 和 $b$。你可以进行如下操作：

- 选择一个下标 $i$（$1 \le i \le n$），将 $a_i$ 和 $b_i$ 交换。

你可以进行任意次数的操作（也可以一次都不做），但每个下标最多只能被选择一次。你的任务是，在所有操作完成后，使得 $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$ 个数，依次为每次操作所选择的下标。

要求每个下标最多被选择一次。

若存在多种可行方案，可以输出任意一种。

输入输出样例

输入 #1
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
输出 #1
2
2 4
-1
0

2
3 4
C++ 编辑器
输入
输出