传送门
首先判断每个数是否都恰好出现了两次。如果满足上述条件，那么肯定可以经过有限次交换变成两行排列。
根据2-SAT的思想进行建边。
然后每次dfs(dfs过程中不会碰到同一个数)的时候判断当前点的行位置,记录dfs过程中出现在第一行和第二行中的元素个数(它们满足都在不同列),取计数较小的那个行中的列位置进行交换即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=400005;
int pos[MAXN][2];
int n;
#define MAXM 400005
struct{int to;int val;int nxt;
}edge[MAXM*2];
int edgecnt=1;
int head[MAXN];
void addedge(int u,int v,int w)
{edge[++edgecnt].to=v;edge[edgecnt].val=w;edge[edgecnt].nxt=head[u];head[u]=edgecnt;
}
int vis[MAXN];
void init()
{edgecnt=1;for (int i = 0; i < 2*n;++i) {head[i]=0;vis[i]=0;pos[i][0]=pos[i][1]=-1;}
}int a[MAXN];
int cmp[2];
vector<int>out[2];
vector<int>put;
void dfs(int x)
{cmp[x/n]++;vis[a[x]]=1;out[x/n].push_back(x%n+1);for(int i=head[x];i;i=edge[i].nxt){int to=edge[i].to;if(vis[a[to]])continue;dfs(to);}
}
int main()
{//freopen("E://tt.txt","r",stdin);ios::sync_with_stdio(false);int t;cin>>t;while(t--){cin>>n;int boolean=1;init();for (int i = 0; i < n; ++i) {int x;cin>>x;a[i]=x;if(x<1||x>n)boolean=0;if(pos[x][0]==-1)pos[x][0]=i;else if(pos[x][1]==-1)pos[x][1]=i;else boolean=0;}for (int i = n; i <2*n; ++i) {int x;cin>>x;a[i]=x;if(x<1||x>n)boolean=0;if(pos[x][0]==-1)pos[x][0]=i;else if(pos[x][1]==-1)pos[x][1]=i;else boolean=0;}if(!boolean){cout<<"-1"<<endl;continue;}ll ans=0;for (int i = 1; i <= n; ++i) {if((pos[i][1]-pos[i][0])==n)continue;int x=pos[i][0];int y=pos[i][1];addedge(x,(y+n)%(2*n),0);addedge(y,(x+n)%(2*n),0);}put.clear();for (int i = 0; i <2*n; ++i) {if(vis[a[i]])continue;out[0].clear();out[1].clear();cmp[0]=cmp[1]=0;dfs(i);ans+=min(cmp[0],cmp[1]);int flag=(cmp[0]>=cmp[1]);for (int j = 0; j < out[flag].size(); ++j) {put.push_back(out[flag][j]);}}cout<<ans<<endl;for (int i = 0; i < put.size(); ++i) {cout<<put[i]<<" ";}cout<<endl;}
}