#include"sorting.h"
#include<bits/stdc++.h>
using namespace std;
int n;
int dist(vector<int> a, vector<int> b){
vector<int> marc(a.size(),0);
vector<int> rb(b.size());
for(int i=0;i<n;i++){
rb[b[i]]=i;
}
int d=n;
for(int i=0;i<n;i++){
int at=a[i];
if(marc[at])continue;
d--;
while(!marc[at]){
marc[at]=1;
at=a[rb[at]];
}
}
return d;
}
int findSwapPairs(int N, int s[], int M, int x[], int y[], int P[], int Q[]){
n=N;
vector<int> ord(n);
vector<int> vec(n);
for(int i=0;i<n;i++)vec[i]=s[i];
int l=0;int r=n+1;
while(l<=r){
int m=(l+r)/2;
iota(ord.begin(),ord.end(),0);
for(int i=m-1;i>=0;i--){
swap(ord[x[i]],ord[y[i]]);
}
int d=dist(vec,ord);
if(d<=m){
r=m-1;
}
else{
l=m+1;
}
}
int rp=r+1;
iota(ord.begin(),ord.end(),0);
for(int i=rp-1;i>=0;i--){
swap(ord[x[i]],ord[y[i]]);
}
vector<int> marc(n,0);
vector<pair<int,int>> trocas;
vector<int> rv(n);
for(int i=0;i<n;i++){
rv[vec[i]]=i;
}
for(int i=0;i<n;i++){
if(marc[ord[i]])continue;
int at=ord[i];
marc[at]=1;
int vai=ord[rv[at]];
if(at==vai)continue;
while(vai!=ord[i]){
marc[vai]=1;
trocas.push_back({at,vai});
at=vai;
vai=ord[rv[vai]];
}
}
vector<int> at(n);
vector<int> onde(n);
vector<pair<int,int>> resp;
at=vec;
for(int i=0;i<n;i++){
onde[at[i]]=i;
}
for(int i=0;i<trocas.size();i++){
swap(at[x[i]],at[y[i]]);
swap(onde[at[x[i]]],onde[at[y[i]]]);
resp.push_back({onde[trocas[i].first],onde[trocas[i].second]});
}
while(resp.size()!=rp){
resp.push_back({0,0});
}
for(int i=0;i<rp;i++){
P[i]=resp[i].first;
Q[i]=resp[i].second;
}
return rp;
}
