#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
#define SZ(x) int(x.size())
const int MAXN = 2e5 + 10;
int cnt , to[MAXN] , mark[MAXN];
vector<int> vec , adj[MAXN];
void DFS(int v){
mark[v] = 1;
vec.push_back(v);
for(int u : adj[v]){
if(!mark[u]) DFS(u);
}
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
for(int i = 0 ; i < N ; i++) to[i] = i;
for(int i = 0 ; i < M ; i++){
swap(S[X[i]] , S[Y[i]]);
}
for(int i = 0 ; i < N ; i++){
adj[i].push_back(S[i]);
// cout << S[i] << ' ';
}
// cout << endl;
for(int i = 0 ; i < N ; i++){
if(!mark[i]){
vec.clear();
DFS(i);
for(int j = 1 ; j < SZ(vec) ; j++){
P[cnt] = vec[0];
Q[cnt] = vec[j];
cnt++;
}
}
}
for(int i = M - 1 ; i >= 0 ; i--){
if(i < cnt){
P[i] = to[P[i]];
Q[i] = to[Q[i]];
}
swap(to[X[i]] , to[Y[i]]);
}
return cnt;
}
