#include "sorting.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define pii pair<int,int>
#define all(a) a.begin(),a.end()
#define S second
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld long double
#define ll long long
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 5e5 + 100 , inf = 1e9+ 10 , mod = 1e9 + 7 ;
int b[maxn] , n , a[maxn] , o[maxn] , c[maxn], B[maxn] , ID[maxn] , P[maxn] , Q[maxn] , x[maxn] , y[maxn] , S[maxn];
int sl(int z){
rep(i , 0 ,n-1){
a[i] = S[i] ;
b[i] = S[i] ;
ID[a[i]] = i ;
}
rep(i ,0 ,z){
swap(b[x[i]] , b[y[i]]) ;
}
vector <pii> vec ;
rep(i , 0, n-1){
while(b[i] != i){
vec.pb({b[i] , b[b[i]]}) ;
swap(b[i] , b[b[i]]) ;
}
}
if(sz(vec) > z+1) return 0 ;
rep(i , 0 ,z){
swap(a[x[i]] , a[y[i]]);
swap(ID[a[x[i]]] , ID[a[y[i]]]);
if(i < sz(vec)){
P[i] = ID[vec[i].F] ;
Q[i] = ID[vec[i].S] ;
} else{
P[i] = Q[i] = 0;
}
swap(a[P[i]] , a[Q[i]]) ;
swap(ID[a[P[i]]], ID[a[Q[i]]]) ;
}
return 1;
}
int findSwapPairs(int N, int SS[], int m, int X[], int Y[], int p[], int q[]){
n = N ;
rep(i , 0 , m-1){
x[i] = X[i] ;
y[i] = Y[i] ;
}
rep(i , 0 ,n-1){
S[i] = SS[i] ;
}
int l = -1 , r = n;
while(r-l > 1){
int mid = (l+r)/2 ;
if(sl(mid-1) == 1){
r = mid ;
}else{
l = mid ;
}
}
sl(r-1) ;
rep(i , 0 ,r-1){
p[i] = P[i] ;
q[i]= Q[i];
}
return r ;
}
