#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int dfs(int x, vector<int>& g, vector<bool>& vis) {
vis[x]=1;
if(!vis[g[x]]) {
return dfs(g[x], g, vis)+1;
}
return 1;
}
void dfsv(int x, vector<int>& g, vector<bool>& vis, vector<int>& vec) {
vis[x]=1;
vec.push_back(x);
if(!vis[g[x]]) {
dfsv(g[x], g, vis, vec);
}
}
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
vector<int> t;
for(int i=0; i<n; ++i) {
t.push_back(s[i]);
}
int lo = 0, hi = m, len=m;
while(lo<=hi) {
int l = (lo+hi)/2;
vector<bool> vis(n);
for(int i=0; i<n; ++i) {
t[i]=s[i];
}
for(int i=0; i<l; ++i) {
swap(t[x[i]], t[y[i]]);
}
int cnt=0;
for(int i=0; i<n; ++i) {
if(!vis[i]) {
cnt += dfs(i, t, vis)-1;
}
}
if(cnt<=l) {
len=l;
hi=l-1;
}
else {
lo=l+1;
}
}
for(int i=0; i<n; ++i) {
t[i]=s[i];
}
//~ for(int i=0; i<n; ++i) {
//~ cerr<<t[i]<<' ';
//~ }
//~ cerr<<'\n';
for(int i=0; i<len; ++i) {
swap(t[x[i]], t[y[i]]);
}
vector<int> wrong, pos(n), fin(n), where(n);
vector<bool> vis(n);
for(int i=0; i<n; ++i) {
if(t[i]!=i && !vis[i]) {
vector<int> vec;
dfsv(i, t, vis, vec);
reverse(vec.begin(), vec.end());
for(int j: vec) wrong.push_back(t[j]);
}
pos[s[i]]=i;
}
for(int i=0; i<n; ++i) {
fin[i]=pos[t[i]];
where[pos[t[i]]]=i;
}
for(int i=0; i<n; ++i) {
t[i]=s[i];
}
//~ cerr<<"fin: ";
//~ for(int i=0; i<n; ++i) cerr<<where[i]<<' ';
//~ cerr<<'\n';
//~ cerr<<"wrong: ";
//~ for(int i: wrong) cerr<<i<<' ';
//~ cerr<<'\n';
for(int i=0; i<len; ++i) {
p[i]=q[i]=0;
}
reverse(wrong.begin(), wrong.end());
for(int i=0; i<len; ++i) {
swap(t[x[i]], t[y[i]]);
swap(pos[t[x[i]]], pos[t[y[i]]]);
swap(fin[where[x[i]]], fin[where[y[i]]]);
swap(where[x[i]], where[y[i]]);
while(wrong.size() && fin[pos[wrong.back()]]==wrong.back()) {
wrong.pop_back();
}
if(wrong.empty()) break;
int u = wrong.back();
wrong.pop_back();
//~ cerr<<len-i<<' '<<u<<' '<<pos[u]<<' '<<fin[u]<<'\n';
p[i]=pos[u];
q[i]=fin[u];
swap(t[p[i]], t[q[i]]);
swap(pos[t[p[i]]], pos[t[q[i]]]);
}
//~ cerr<<len<<'\n';
//~ for(int i=0; i<len; ++i) {
//~ cerr<<p[i]<<' '<<q[i]<<'\n';
//~ }
//~ for(int i=0; i<len; ++i) {
//~ swap(s[x[i]], s[y[i]]);
//~ swap(s[p[i]], s[q[i]]);
//~ }
//~ for(int i=0; i<n; ++i) {
//~ cerr<<s[i]<<' ';
//~ }
//~ cerr<<'\n';
return len;
}
