【題解】Codeforces 1385G. Columns Swaps

#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";
    }
}