CFCF2192E.Swap to Rearrange

提高+/省选-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

给定两个长度为 nn 的数组 aabb。你可以进行如下操作:

  • 选择一个下标 ii1in1 \le i \le n),将 aia_ibib_i 交换。

你可以进行任意次数的操作(也可以一次都不做),但每个下标最多只能被选择一次。你的任务是,在所有操作完成后,使得 aa 成为 bb 的一个重排列,或者说明这不可能做到。你不需要最小化操作次数。

输入格式

每组测试数据包含多个测试用例。第一行包含测试用例数 tt1t1041 \le t \le 10^4)。接下来是每个测试用例的描述。

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

第二行包含 nn 个整数 a1,a2,,ana_1,a_2,\ldots,a_n1ain1 \leq a_i \leq n)。

第三行包含 nn 个整数 b1,b2,,bnb_1,b_2,\ldots,b_n1bin1 \leq b_i \leq n)。

保证所有测试用例中 nn 的总和不超过 10610^6

输出格式

对于每个测试用例,若无法使 aa 成为 bb 的一个重排列,则输出 1-1。否则,按如下格式输出两行:

  • 第一行输出操作次数 ss0sn0 \leq s \leq n)。
  • 第二行输出 ss 个数,依次为每次操作所选择的下标。

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

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

输入输出样例

  • 输入#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

说明/提示

在第一个测试用例中,进行了 swap(a2,b2a_2, b_2) 和 swap(a4,b4a_4, b_4) 操作,使得 a=[1,2,3,4]a = [1,2,3,4]b=[2,1,4,3]b = [2,1,4,3]。此时 aa 可以通过重排 bb 得到。

在第二个测试用例中,无论如何操作,都无法使 aa 成为 bb 的一个重排列。

首页