#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
int N,S[200001];
int M,X[600001],Y[600001];
int arr[200001];
bool vis[200001];
int to[200001];
queue<pair<int,int>>q;
int pos[200001];
void dfs(int node){
vis[node]=true;
if (!vis[to[node]]){
dfs(to[node]);
q.push({arr[node],arr[to[node]]});
}
}
bool check(int mid){
while (!q.empty())
q.pop();
for (int i=0;i<N;i++){
arr[i]=S[i];
vis[i]=false;
}
for (int i=1;i<=mid;i++)
swap(arr[X[i]],arr[Y[i]]);
for (int i=0;i<N;i++)
to[i]=arr[i];
int comps=0;
for (int i=0;i<N;i++){
pos[arr[i]]=i;
if (!vis[i]){
comps++;
dfs(i);
}
}
return N-comps<=mid;
}
int findSwapPairs(int n,int s[],int m, int x[], int y[],int P[], int Q[]){
N=n;
for (int i=0;i<N;i++)
S[i]=s[i];
M=m;
for (int i=1;i<=M;i++){
X[i]=x[i];
Y[i]=y[i];
}
int low=-1,high=M+1;
while (low+1<high){
int mid=(low+high)/2;
if (check(mid))
high=mid;
else
low=mid;
}
check(high);
for (int i=high;i>=1;i--){
if (!q.empty()){
P[i]=pos[q.front().first];
Q[i]=pos[q.front().second];
swap(pos[arr[X[i]]],pos[arr[Y[i]]]);
swap(arr[X[i]],arr[Y[i]]);
q.pop();
}
}
return high;
}
