#include "sorting.h"
#include <vector>
#include <iostream>
#define MAXN 200005
using namespace std;
int N, M, goal[MAXN], to[MAXN], P2[MAXN], P[MAXN], eX[MAXN*3], eY[MAXN*3];
int at[MAXN], E[MAXN*3][2]; //which element values to swap
bool vis[MAXN];
int can(int t) {
int swaps = 0, pt = 0;
for (int i=0; i<N; i++) {goal[i]=i;}
for (int i=0; i<t; i++) {swap(goal[eX[i]], goal[eY[i]]);}
for (int i=0; i<N; i++) {vis[i]=0;}
for (int i=0; i<N; i++) {to[i]=goal[i];} //end position aim for element with value i
for (int i=0; i<N; i++) {
if(vis[i]) {continue;}
int cur = i;
swaps--;
vector<int> Elem;
while (!vis[cur]) {
Elem.push_back(P[cur]);
vis[cur]=true, swaps++;
cur = to[P[cur]];
}
while (Elem.size() > 1) {
E[pt][0]=Elem[Elem.size()-1];
E[pt][1]=Elem[Elem.size()-2];
Elem.pop_back();
Elem.pop_back();
Elem.push_back(E[pt][0]);
pt++;
}
}
return(swaps);
}
int findSwapPairs(int n, int S[], int m, int X[], int Y[], int p[], int q[]) {
N=n, M=m;
for (int i=0; i<N; i++) {P[i]=S[i];}
for (int i=0; i<M; i++) {
eX[i]=X[i], eY[i]=Y[i];
}
int lo = -1, hi = m;
while (lo + 1 != hi) {
int mid = (lo + hi) >> 1;
if (can(mid) <= mid) {hi = mid;}
else {lo = mid;}
}
int ans = hi, swaps = can(hi);
for (int i=0; i<n; i++) {
at[S[i]]=i;
P2[i]=P[i];
}
for (int i=0; i<swaps; i++) {
swap(at[P2[X[i]]], at[P2[Y[i]]]);
swap(P2[X[i]], P2[Y[i]]);
p[i] = at[E[i][0]], q[i] = at[E[i][1]];
swap(P2[p[i]], P2[q[i]]);
swap(at[E[i][0]],at[E[i][1]]);
}
for (int i=swaps; i<ans; i++) {
p[i]=q[i]=0;
}
return(ans);
}
