#include<bits/stdc++.h>
using namespace std;
int GetReqMoves(vector<int> Base){
int a=0;
vector<bool> Visited(Base.size(),false);
for(int i=0;i<Base.size();i++){
if(Visited[i]==false){
a++;
Visited[i]=true;
int j=Base[i];
while(j!=i){
Visited[j]=true;
j=Base[j];
}
}
}
return Base.size()-a;
}
vector<vector<int>> GetReqSeq(vector<int> Base){
int a=0;
vector<vector<int>> Ret;
vector<bool> Visited(Base.size(),false);
for(int i=0;i<Base.size();i++){
if(Visited[i]==false){
vector<int> Seq;
a++;
Visited[i]=true;
Seq.push_back(Base[i]);
int j=Base[i];
while(j!=i){
Visited[j]=true;
Seq.push_back(Base[j]);
j=Base[j];
}
Ret.push_back(Seq);
}
}
return Ret;
}
int getIndex(vector<int> BaseSequence,int t){
for(int i=0;i<BaseSequence.size();i++){
if(BaseSequence[i]==t){
return i;
}
}
return 0;
}
int DoMoves(vector<vector<int>> Seq, vector<int> BaseSequence,int* P, int* Q,int* X,int* Y){
int swaps=0;
int temp=BaseSequence[X[swaps]];
BaseSequence[X[swaps]]=BaseSequence[Y[swaps]];
BaseSequence[Y[swaps]]=temp;
swaps++;
int RS=0;
for(int i=0;i<Seq.size();i++){
if(Seq[i].size()>1){
int base=Seq[i][0];
for(int j=1;j<Seq[i].size();j++){
P[RS]=getIndex(BaseSequence,base);
Q[RS]=getIndex(BaseSequence,Seq[i][j]);
int a=BaseSequence[P[RS]];
BaseSequence[P[RS]]=BaseSequence[Q[RS]];
BaseSequence[Q[RS]]=a;
base=Seq[i][j];
RS++;
int temp2=BaseSequence[X[swaps]];
BaseSequence[X[swaps]]=BaseSequence[Y[swaps]];
BaseSequence[Y[swaps]]=temp2;
swaps++;
}
}
}
return RS;
}
int findSwapPairs(int N,int* S,int M,int* X,int* Y,int* P,int* Q){
vector<int> BaseSequence;
for(int i=0;i<N;i++){
BaseSequence.push_back(S[i]);
}
std::vector<int> NewS=BaseSequence;
int i=0;
while(true){
int a=NewS[X[i]];
NewS[X[i]]=NewS[Y[i]];
NewS[Y[i]]=a;
i++;
if(GetReqMoves(NewS)<=i){
int moves = DoMoves(GetReqSeq(NewS),BaseSequence,P,Q,X,Y);
for(int j=moves;j<i;j++){
P[j]=0;
Q[j]=0;
}
return i;
}
}
return i;
}
