#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
vi nxt(N), grp(N), siz(N, 1);
for(int i=0; i<N; ++i) {
nxt[i] = S[i];
grp[i] = i;
}
int cnt = 0;
for(int i=0; i<N; ++i) {
if(grp[i] != i) continue;
++cnt;
int cur = nxt[i];
for(; cur!=i; cur=nxt[cur]) {
grp[cur] = i;
++siz[i];
}
}
vi S2(N);
for(int j=0; j<N; ++j) S2[j] = j;
for(int i=0; i<M; ++i) {
swap(S2[X[i]], S2[Y[i]]);
if(grp[X[i]] == grp[Y[i]] && X[i] != Y[i]) {
swap(nxt[X[i]], nxt[Y[i]]);
if(grp[X[i]] == X[i]) swap(X[i], Y[i]);
int cur = nxt[X[i]];
siz[X[i]] = 1;
for(; cur != X[i]; cur = nxt[cur]) {
grp[X[i]] = X[i];
++siz[X[i]];
}
siz[grp[Y[i]]] -= siz[X[i]];
} else if(X[i] != Y[i]) {
--cnt;
if(siz[grp[X[i]]] < siz[grp[Y[i]]]) swap(X[i], Y[i]);
siz[grp[X[i]]] += siz[grp[Y[i]]];
grp[Y[i]] = grp[X[i]];
int cur = nxt[Y[i]];
for(; cur != Y[i]; cur = nxt[cur]) grp[cur] = grp[X[i]];
swap(nxt[X[i]], nxt[Y[i]]);
}
if((N-cnt) <= i+1) {
vector<pi>swp;
for(int j=0; j<N; ++j) {
if(siz[grp[j]] > 1) {
swp.push_back({j, nxt[j]});
swap(nxt[nxt[j]], nxt[j]);
--siz[grp[j]];
}
}
for(int j=(int)swp.size()-1; j>=0; --j) {
P[j] = S2[swp[j].first];
Q[j] = S2[swp[j].second];
swap(S2[X[j]], S2[Y[j]]);
}
for(int j=(int)swp.size(); j<=i; ++j) P[j] = Q[j] = 0;
return i+1;
}
}
return 1;
}
