#include "bits/stdc++.h"
// #include "grader.cpp"
#include "sorting.h"
using namespace std;
#define ff first
#define ss second
int a[300000], vis[300000], b[300000], vip[300000];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
for(int i = 0; i < N; i++) {
a[i] = S[i];
}
sort(a, a + N);
int f = 1;
for(int i = 0; i < N; i++) {
if(a[i] != S[i]) f = -1;
a[i] = S[i];
}
if(~f) return 0;
for(int i = 0; i < M; i++) {
swap(a[X[i]], a[Y[i]]);
for(int j = 0; j < N; j++) {
b[j] = a[j];
vip[a[j]] = j;
}
deque <pair <int,int>> v, ans;
for(int j = 0; j < N; j++) {
if(b[j] == j) continue;
v.push_back({b[j], b[vip[j]]});
swap(b[j], b[vip[j]]);
swap(vip[j],vip[b[j]]);
}
if((int)v.size() > i + 1) continue;
for(int j = 0; j < N; j++) {
a[j] = S[j];
vis[a[j]] = j;
}
for(int j = 0; j <= i; j++) {
ans.push_back({X[j],Y[j]});
swap(vis[a[X[j]]],vis[a[Y[j]]]);
if((int)v.size()) {
ans.push_back({vis[v[0].ff], vis[v[0].ss]});
swap(vis[v[0].ff], vis[v[0].ss]);
v.pop_front();
}
else {
ans.push_back({0,0});
}
}
for(int j = 0; j < N; j++) {
P[j] = ans[j].ff;
Q[j] = ans[j].ss;
}
return (i + 1) * 2;
}
return 1;
}
