#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#include "sorting.h"
// #include "grader.cpp"
int findSwapPairs(int n, int s[], int m, int X[], int Y[], int P[], int Q[]) {
vector<int> tar(n);
iota(tar.begin(),tar.end(),0);
for(int i=0;i<n;i++) P[i] = Q[i] = 0;
vector<int> tmp(n);
for(int i=0;i<n;i++) tmp[i] = s[i];
for(int i=n-1;i>=0;i--){
swap(tar[X[i]],tar[Y[i]]);
}
// for(auto i : tar) cout<<i<<' ';
// cout<<endl;
vector<int> idx(n);
for(int i=0;i<n;i++){
idx[s[i]] = i;
}
set<int> st;
for(int i=0;i<n;i++){
if(s[i] != tar[i]) st.insert(i);
}
auto do_swap = [&](int i,int j){
int x = s[i] , y = s[j];
if(s[i] != tar[i]) st.erase(i);
if(s[j] != tar[j] && st.count(j)) st.erase(j);
swap(s[i],s[j]);
swap(idx[x],idx[y]);
if(s[i] != tar[i]) st.insert(i);
if(s[j] != tar[j]) st.insert(j);
};
int pt = 0;
// for(auto i : tar) cout<<i<<' ';
// cout<<endl;
for(int i=0;i<n;i++){
do_swap(X[i],Y[i]);
if(tar[X[i]] != s[X[i]]) st.erase(X[i]);
if(tar[Y[i]] != s[Y[i]] && st.count(Y[i])) st.erase(Y[i]);
swap(tar[X[i]],tar[Y[i]]);
if(tar[X[i]] != s[X[i]]) st.insert(X[i]);
if(tar[Y[i]] != s[Y[i]]) st.insert(Y[i]);
if(st.size()){
int pt = *st.begin();
P[i] = pt , Q[i] = idx[tar[pt]] , do_swap(pt,idx[tar[pt]]);
}
}
for(int i=0;i<n;i++) {
swap(tmp[X[i]],tmp[Y[i]]);
swap(tmp[P[i]],tmp[Q[i]]);
}
// for(auto i : tmp) cout<<i<<' ';
// cout<<endl;
return n;
}
