#include "sorting.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=2e5+10;
int f[maxn], marc[maxn], finalizar[maxn], aa[maxn], bb[maxn], cnt, qm[maxn], tmp[maxn], qtd_ciclo, N, pai[maxn], tam[maxn];
vector<pii>seg[4*maxn];
int find(int a){
if(pai[a]==a) return a;
return find(pai[a]);
}
void merge(int a, int b){
// cerr << "+ " << a << ' ' << b << '\n';
pai[a]=b;
tam[b]+=tam[a];
qtd_ciclo--;
}
void roll_back(int a, int b, int ta, int tb){
pai[a]=a; pai[b]=b;
tam[a]=ta; tam[b]=tb;
qtd_ciclo++;
}
void dfs(int u){
marc[u]++;
if(!marc[f[u]]) dfs(f[u]);
}
void get(int u){
finalizar[u]++;
if(!finalizar[f[u]]){
aa[cnt]=u; bb[cnt]=f[u];
cnt++;
get(f[u]);
}
}
void add(int id, int ini, int fim, int l, int r, pii p){
if(ini>r||fim<l) return;
if(l<=ini&&fim<=r){
seg[id].push_back(p);
return;
}
int mid=(ini+fim)/2, e=2*id, d=2*id+1;
add(e,ini,mid,l,r,p); add(d,mid+1,fim,l,r,p);
}
void undo(stack<pair<pii,pii>>fiz){
while(fiz.size()){
pair<pii,pii>u=fiz.top(); fiz.pop();
roll_back(u.fi.fi,u.fi.se,u.se.fi,u.se.se);
}
}
int calc(int id, int ini, int fim){
stack<pair<pii,pii>>fiz;
for(pii p : seg[id]){
int a=find(p.fi), b=find(p.se);
if(a==b) continue;
if(tam[a]>tam[b]) swap(a,b);
fiz.push({{a,b},{tam[a],tam[b]}});
merge(a,b);
}
if(ini==fim){
// cerr << ini << ' ' << qtd_ciclo << '\n';
int ret=maxn;
if(N-qtd_ciclo<=ini+1) ret=ini;
undo(fiz);
return ret;
}
int mid=(ini+fim)/2, e=2*id, d=2*id+1;
int ret=min(calc(e,ini,mid),calc(d,mid+1,fim));
undo(fiz);
return ret;
}
int findSwapPairs(int n, int s[], int m, int X[], int Y[], int P[], int Q[]){
N=n;
qtd_ciclo=n;
for(int i=0;i<n;i++) pai[i]=i, tam[i]=1;
int og[n], aux[n];
for(int i=0;i<n;i++) og[s[i]]=i, aux[i]=s[i];
// fzr a conectividade dinamica logo aaaa
for(int i=0;i<n;i++) qm[i]=s[i];
for(int i=0;i<n;i++){
add(1,0,n-1,tmp[X[i]],i-1,{X[i],qm[X[i]]});
add(1,0,n-1,tmp[Y[i]],i-1,{Y[i],qm[Y[i]]});
swap(qm[X[i]],qm[Y[i]]);
tmp[X[i]]=tmp[Y[i]]=i;
}
for(int i=0;i<n;i++) add(1,0,n-1,tmp[i],n-1,{i,qm[i]});
cnt=0;
auto check=[&](int z[]){
for(int i=1;i<n;i++) if(z[i-1]>z[i]) return false;
return true;
};
if(check(s)) return 0;
auto finish=[&](int i){
// cerr << "da pra fzr em: " << i+1 << '\n';
// cerr << "s: ";
// for(int j=0;j<n;j++) cerr << s[j] << ' ';
// cerr << '\n';
// cerr << "f: ";
// for(int j=0;j<n;j++) cerr << f[j] << ' ';
// cerr << '\n';
// cerr << "og: ";
// for(int j=0;j<n;j++) cerr << og[j] << ' ';
// cerr << '\n';
// cerr << "aux: ";
// for(int j=0;j<n;j++) cerr << aux[j] << ' ';
// cerr << '\n';
for(int j=0;j<n;j++) if(!finalizar[j]) get(j);
for(int j=0;j<=i;j++){
swap(og[aux[X[j]]],og[aux[Y[j]]]);
swap(aux[X[j]],aux[Y[j]]);
P[j]=og[aa[j]]; Q[j]=og[bb[j]];
// cerr << "swap " << aa[i] << ' ' << bb[j] << '\n';
swap(og[aa[j]],og[bb[j]]);
swap(aux[og[aa[j]]],aux[og[bb[j]]]);
// cerr << "aux: ";
// for(int j=0;j<n;j++) cerr << aux[j] << ' ';
// cerr << '\n';
}
assert(check(aux));
return i+1;
}; // chamar finish(x), se tem certeza que eh possivel fzr em i passos. OBS: deixar os f's de maneira certa antes, para que o get() funcione
int qtd=calc(1,0,n-1);
for(int i=0;i<n;i++) s[i]=aux[i];
for(int i=0;i<=qtd;i++) swap(s[X[i]],s[Y[i]]);
for(int i=0;i<n;i++) f[i]=s[i];
return finish(qtd);
}
