Columns Swaps_综合

You are given a table a of size $2×n$ (i.e. two rows and n columns) consisting of integers from $1$ to $n$ .

In one move, you can choose some column $j$ $(1≤j≤n)$ and swap values $a_{1,j}$ and $a_{2,j}$ in it. Each column can be chosen no more than once.

Your task is to find the minimum number of moves required to obtain permutations of size $n$ in both first and second rows of the table or determine if it is impossible to do that.

You have to answer $t$ independent test cases.

Recall that the permutation of size $n$ is such an array of size $n$ that contains each integer from $1$ to $n$ exactly once (the order of elements doesn’t matter).

Input
The first line of the input contains one integer $t$ $(1≤t≤2?10^4)$ — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ $(1≤n≤2?10^5)$ — the number of columns in the table. The second line of the test case contains $n$ integers $a_{1,1},a_{1,2},…,a_{1,n}$ $(1≤a_{1,i}≤n)$ , where $a_{1,i}$ is the i-th element of the first row of the table. The third line of the test case contains $n$ integers $a_{2,1},a_{2,2},…,a_{2,n}$ $(1≤a_{2,i}≤n)$ , where $a_{2,i}$ is the $i$ -th element of the second row of the table.

It is guaranteed that the sum of $n$ does not exceed $2?10^5$ $(∑n≤2?10^5)$ .

Output
For each test case print the answer: $-1$ if it is impossible to obtain permutation of size $n$ in both first and the second rows of the table, or one integer $k$ in the first line, where $k$ is the minimum number of moves required to obtain permutations in both rows, and $k$ distinct integers $pos_1,pos_2,…,pos_k$ in the second line $(1≤pos_i≤n)$ in any order — indices of columns in which you need to swap values to obtain permutations in both rows. If there are several answers, you can print any.

Example

首先，如果不是每个数都出现恰好出现 $2$ 次，那么一定无解输出 $-1$ 。
否则，按照 $2-SAT$ 思想，设 $i$ 表示第 $i$ 列不交换； $i+n$ 表示第 $i$ 列交换。
对于某个数 $x$ ， $x$ 出现的两个位置的列 $i,j\ (i\not =j)$ ，如果两个位置的 $x$ 在相同行，那么第 $i$ 列交换是第 $j$ 列不交换的充要条件；如果两个位置不同行，那么第 $i$ 列交换是第 $j$ 列交换的充要条件。
根据描述连边，然后跑 $2-SAT$ 。
可惜由于 $2-SAT$ 是按 $dfs$ 序构造解，因此输出的是一个可行解，而不是交换次数最少的解。
这里注意到，只要满足每个数都出现恰好出现 $2$ 次，就一定有解，这里可以用反证法证明一下。
并且形成的每一个连通块是强连通的，因此每个连通块内的方案是确定的；
且每个连通块都有对称的连通块。
这里两个连通块对称是指对于某个连通块上的点 $x$ ，如果 $x<n$ ，则换成 $x+n$ ；如果 $x>n$ 则换成 $x-n$ ，转换后的连通块与原连通块对称。
这样，可以遍历每个连通块，求出大于 $n$ 的点数量，如果，这样的点占一多半，因为有对称的连通块，因此可以取另一部分。
最终得到的一定是至少交换方案。
时间复杂度为 $O(n)$ 。

#include<bits/stdc++.h>#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define sc(a) scahf("%c",&a);
#define ss(a) scanf("%s",a)
#define pi(a) printf("%d\n",a)
#define pl(a) printf("%lld\n",a)
#define pc(a) putchar(a)
#define ms(a) memset(a,0,sizeof(a))
#define repi(i, a, b) for(register int i=a;i<=b;++i)
#define repd(i, a, b) for(register int i=a;i>=b;--i)
#define reps(s) for(register int i=head[s];i;i=Next[i])
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define pii pair<int,int>
#define mii unordered_map<int,int>
#define msi unordered_map<string,int>
#define lowbit(x) ((x)&(-(x)))
#define ce(i, r) i==r?'\n':' '
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define INF 0x3f3f3f3f
#define pr(x) cout<<#x<<": "<<x<<endl
using namespace std;inline int qr() {int f = 0, fu = 1;char c = getchar();while (c < '0' || c > '9') {if (c == '-')fu = -1;c = getchar();}while (c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + c - 48;c = getchar();}return f * fu;
}const int N = 2e5 + 10;
int head[N << 1], ver[N << 2], Next[N << 2], tot;
vector<pii > pos[N];
int T, n, cnt, ans;
bool v1[N << 1], v2[N];
vi tmp;inline void init() {tot = ans = 0;memset(head, 0, sizeof(int) * n * 2 + 10);memset(v1, false, sizeof(bool) * n * 2 + 10);memset(v2, false, sizeof(bool) * n + 10);repi(i, 1, n)pos[i].clear();
}inline void add(int x, int y) {ver[++tot] = y;Next[tot] = head[x];head[x] = tot;
}inline bool read() {bool suc = true;repi(i, 1, 2)repi(j, 1, n) {int x = qr();if (pos[x].size() == 2) suc = false;pos[x].pb({i, j});}return suc;
}void dfs(int x) {v1[x] = true;if (x > n)v1[x - n] = true, tmp.pb(x - n), v2[x - n] = true, cnt++;else tmp.pb(x);reps(x)if (!v1[ver[i]])dfs(ver[i]);
}inline void build() {repi(i, 1, n) {if (pos[i][0].se == pos[i][1].se)continue;if (pos[i][0].fi == pos[i][1].fi) {add(pos[i][0].se, pos[i][1].se + n);add(pos[i][0].se + n, pos[i][1].se);add(pos[i][1].se, pos[i][0].se + n);add(pos[i][1].se + n, pos[i][0].se);} else {add(pos[i][0].se + n, pos[i][1].se + n);add(pos[i][0].se, pos[i][1].se);add(pos[i][1].se + n, pos[i][0].se + n);add(pos[i][1].se, pos[i][0].se);}}
}inline void solve() {repi(i, 1, n)if (!v1[i]) {cnt = 0, tmp.clear(), dfs(i);if (cnt * 2 > tmp.size()) {for (auto it:tmp)v2[it] ^= 1;cnt = tmp.size() - cnt;}ans += cnt;}
}int main() {T = qr();int cse = 0;while (T--) {n = qr();init();if (!read()) {puts("-1");continue;}build();solve();pi(ans);repi(i, 1, n)if (v2[i])printf("%d ", i);puts("");}return 0;
}