#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<len; ++i) {
swap(t[x[i]], t[y[i]]);
}
vector<int> wrong, pos(n), T=t, POS(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;
POS[t[i]]=i;
}
for(int i=0; i<n; ++i) {
t[i]=s[i];
}
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]]]);
while(wrong.size() && T[wrong.back()]==wrong.back()) { // update
wrong.pop_back();
}
if(wrong.empty()) break;
int u = wrong.back();
wrong.pop_back();
p[i]=pos[u];
q[i]=pos[T[u]];
swap(t[p[i]], t[q[i]]);
swap(pos[t[p[i]]], pos[t[q[i]]]);
swap(T[POS[u]], T[u]); // zamień miejscami gościa z wartością 'u' i gościa, który na końcu jest na pozycji 'u'
swap(POS[u], POS[T[u]]);
}
return len;
}
