#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX=200000;
int n,m;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n=N,m=M;
vector<int> v(n),need(n);
vector<pair<int,int>> swaps;
for(int i=0;i<n;i++)v[i]=S[i],need[i]=i;
vector<int> tov=need;
for(int j=0;j<m;j++){
swap(tov[X[j]],tov[Y[j]]);
}
vector<int> tov1(n);
for(int i=0;i<n;i++)tov1[tov[i]]=i;
swap(tov,tov1);
for(int i=0;i<m;i++){
swap(v[X[i]],v[Y[i]]);
swap(tov[X[i]],tov[Y[i]]);
bool ok=0;
for(int k=0;k<n;k++){
if(tov[k]!=v[k]){
for(int j=0;j<n;j++){
if(tov[j]==v[k]){
ok=1;
swaps.push_back({k,j});
swap(v[k],v[j]);
break;
}
}
if(ok)break;
}
if(ok)break;
}
if(!ok)swaps.push_back({0,0});
}
// for(int x:v)cout<<x<<" ";
// cout<<"\n";
assert(v==need);
for(int i=0;i<m;i++){
P[i]=swaps[i].first;
Q[i]=swaps[i].second;
}
return M;
}
