# 【題解】Codeforces 1385G. Columns Swaps

【範例】2-SAT（例2）
【題目敘述】http://codeforces.com/contest/1385/problem/G
【解題想法】並查集 + 2-SAT

```#include <iostream>
#include <vector>
using namespace std;

int t, n, x, a[200005][2], p[400005];

int f(int x){
if (p[x] <= 0) return x;
else return p[x] = f(p[x]);
}
int tr(int x){
if (x <= n) return x+n;
else return x-n;
}
void merge(int a, int b){
a = f(a);
b = f(b);
if (a != b){
p[a] += p[b];
p[b] = a;
}
}

int main() {
cin >> t;
while (t--){
cin >> n;
for (int i = 1; i <= n; i++){
a[i][0] = 0;
a[i][1] = 0;
p[i] = -1;
p[i+n] = 0;
}
int tmp = 1;
for (int i = 0; i < 2; i++){
for (int j = 1; j <= n; j++){
cin >> x;
if (!a[x][0]) a[x][0] = tmp;
else if (!a[x][1]) a[x][1] = tmp;
else tmp = 1e9;
tmp++;
}
}
if (tmp >= 1e9){
cout << -1 << "\n";
continue;
}
for (int i = 1; i <= n; i++){
int x = min(tr(a[i][0]), a[i][0]);
int y = min(tr(a[i][1]), a[i][1]);
if ((a[i][0] <= n) == (a[i][1] <= n)){
merge(tr(x), y);
merge(tr(y), x);
}
else{
merge(tr(x), tr(y));
merge(x, y);
}
}
bool flag = true;
for (int i = 1; i <= n; i++){
if (f(i) == f(tr(i))){
cout << -1 << "\n";
flag = false;
break;
}
}
if (!flag) continue;
vector <int> v;
for (int i = 1; i <= n; i++){
int x = f(i);
int y = f(tr(i));
if (p[x] > p[y]){
v.push_back(i);
}
else if (p[x] == p[y] && x < y){
v.push_back(i);
}
}
cout << v.size() << "\n";
for (int i:v){
cout << i << " ";
}
cout << "\n";
}
}
```