#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+100;
int n, ss[N], m, x[N], y[N], p[N], q[N];
int tmp[N];
int solve(int M) {
for(int i = 0; i < n; i++)
tmp[i] = ss[i];
for(int i = 0; i < M; i++)
swap(tmp[x[i]], tmp[y[i]]);
int cur = 0, R = 0;
for(int i = 0; i < n; ) {
if(tmp[i] == i) { i++; continue; }
int pp = i, qq = tmp[i];
for(int j = M-1; j > cur; j--) {
if((x[j] == pp && y[j] == qq) || (x[j] == qq && y[j] == pp)) swap(pp, qq);
else {
if(x[j] == pp) pp = y[j];
else if(y[j] == pp) pp = x[j];
if(x[j] == qq) qq = y[j];
else if(y[j] == qq) qq = x[j];
}
}
p[R] = pp, q[R] = qq;
R++, cur++;
swap(tmp[i], tmp[tmp[i]]);
}
return R;
}
int findSwapPairs(int _n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = _n, m = M;
for(int i = 0; i < n; i++)
ss[i] = S[i];
for(int i = 0; i < m; i++)
x[i] = X[i], y[i] = Y[i];
int R = solve(M);
for(int i = 0; i < R; i++)
P[i] = p[i], Q[i] = q[i];
return R;
}
