#CW62. 列交换(columns)

列交换(columns)

题目描述

给定一个有 nn 列、两行的表格。第 ii 列的上方和下方分别是两个整数;列编号从左到右为 11 到 nn。每个整数都在 11 到 nn 之间,但不保证每个整数恰好出现两次;同一个整数可能在某一行中重复出现,也可能在两行中出现不同次数。

交换只会改变数字所在的行,不会改变它在整个表格中的总出现次数。因此,若某个数的总出现次数不等于 22,这一组数据一定无解;即使每个数都出现两次,也仍需进一步判断是否能通过交换满足要求。

你可以选择若干列,每个被选列至多操作一次;操作是交换这一列的上下两个数。交换完成后,要求上面一行和下面一行都恰好包含 11 到 nn 各一次,也就是说两行都必须是 nn 个元素的排列。请先求达到要求所需的最少交换列数,再给出任意一个达到这个最少值的列集合。如果无论怎样交换都无法达到要求,则该组数据无解。

输入格式

从 columns.in 文件中读入。

第一行是测试组数 tt。每组数据先给出列数 nn,随后给出上面一行的 nn 个整数和下面一行的 nn 个整数。输入保证所有测试组的列数之和不超过 2×1052\times 10^5,且给出的整数均在 11 到 nn 之间。

输出格式

从 columns.out 文件中输出。

如果无解,输出一行 −1-1。否则先输出最少交换次数 kk;随后输出 kk 个被交换的列编号。列编号可以按任意顺序给出,答案只要确实使两行成为排列且 kk 最小即可。

样例 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

样例 1 解释

  • 第 11 组已经满足要求,不需要交换。
  • 第 22 组交换第 2,32,3 列后,两行分别为 (5,2,3,1,4)(5,2,3,1,4) 和 (1,3,5,2,4)(1,3,5,2,4)。
  • 第 33 组交换第 11 列后,两行分别为 (3,2,1)(3,2,1) 和 (1,3,2)(1,3,2)。
  • 第 44 组交换第 3,43,4 列后,两行分别为 (1,2,3,4)(1,2,3,4) 和 (3,4,2,1)(3,4,2,1)。
  • 第 55 组交换第 3,43,4 列后,两行分别为 (4,3,2,1)(4,3,2,1) 和 (3,2,1,4)(3,2,1,4)。
  • 第 66 组无解。

样例输出中的列编号只是其中一种合法方案,任何达到最少交换次数且合法的列集合都会被接受。

数据范围

对全部数据,1≤t≤2×1041\le t\le 2\times 10^4,1≤n≤2×1051\le n\le 2\times 10^5,且 ∑n≤2×105\sum n\le 2\times 10^5。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 25 1∼51\sim 5 n≤12n\le 12
2 6∼106\sim 10 n≤200n\le 200
3 11∼1511\sim 15 n≤2000n\le 2000
4 16∼2016\sim 20 完整数据范围