#include "sorting.h"
#include <iostream>
#include <vector>
using namespace std;
int x[200005];
int y[200005];
int vec[200005];
int vec2[200005];
int fre[200005];
vector<int>ciclu;
void dfs(int poz)
{
if(fre[poz]==1)
{
return;
}
fre[poz]=1;
ciclu.push_back(poz);
dfs(vec2[poz]);
}
vector<pair<int,int> > solve(int nroper,int n)
{
vector<pair<int,int>>oper;
for(int i=0;i<n;i++)
{
fre[i]=0;
vec2[i]=vec[i];
}
/*
for(int i=0;i<nroper;i++)
{
swap(vec2[x[i]],vec2[y[i]]);
}*/
for(int i=0;i<n;i++)
{
if(fre[i]==0)
{
ciclu.clear();
dfs(i);
for(int j=1;j<ciclu.size();j++)
{
oper.push_back({ciclu[0],ciclu[j]});
}
}
}
return oper;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
for(int i=0; i<N; i++)
{
vec[i]=S[i];
}
for(int i=0; i<M; i++)
{
x[i]=X[i];
y[i]=Y[i];
}
vector<pair<int,int> >rez=solve(M,N);
for(int i=0;i<rez.size();i++)
{
P[i]=rez[i].first;
Q[i]=rez[i].second;
}
return rez.size();
}
