/// Black lives matter
#include <bits/stdc++.h>
#include "sorting.h"
/// 500 485 462 A4
using namespace std;
typedef int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=6e5+100;
ll W[N];
ll koj[N];
ll ans1[N],ans2[N];
ll check(ll tool,int32_t n,int32_t s[],int32_t m,int32_t x[],int32_t y[]){
for (int i=0;i<N;i++) par[i]=i;
for (int i=0;i<n;i++) W[i]=s[i];
for (int i=0;i<tool;i++){
swap(W[x[i]],W[y[i]]);
}
for (int i=0;i<n;i++){
koj[W[i]]=i;
}
vector <pii> cng;
for (int i=0;i<n;i++){
if (koj[i]!=i){
cng.pb({W[i],i});
// if (tool==3) cout << W[i] << " tool " << i << endl;
swap(W[koj[i]],W[i]);
ll z=koj[i];
koj[i]=i;
koj[W[z]]=z;
}
}
for (int i=0;i<n;i++){
W[i]=s[i];
}
for (int i=0;i<tool;i++){
swap(W[x[i]],W[y[i]]);
}
for (int i=0;i<n;i++){
koj[W[i]]=i;
}
/*
if (tool==3){
for (int i=0;i<n;i++){
cout << W[i] << " W ";
}
cout << endl;
for (int i=0;i<n;i++){
cout << koj[i] << " koj ";
}
cout << endl;
}
*/
// cout << cng.size() << " " << tool << endl;
if (cng.size()>tool) return 0;
reverse(cng.begin(),cng.end());
for (int i=tool-1;i>-1;i--){
ans1[i]=koj[cng.back().F];
ans2[i]=koj[cng.back().S];
pii p=cng.back();
cng.pop_back();
swap(W[x[i]],W[y[i]]);
swap(koj[W[x[i]]],koj[W[y[i]]]);
if (ans1[i]>ans2[i]) swap(ans1[i],ans2[i]);
if (cng.size()==0) break;
}
return 1;
}
int32_t findSwapPairs(int32_t n, int32_t s[], int32_t m, int32_t x[], int32_t y[], int32_t p[], int32_t q[]) {
/// yadet nare W=s koni
ll p1=0;
for (int i=1;i<n;i++) if (s[i]<s[i-1]) p1=1;
if (p1==0) return 0;
ll l=0,r=m;
while(r-l>1){
// cout << l << " " << r << endl;
ll mid=(r+l)/2;
if (check(mid,n,s,m,x,y)) r=mid;
else l=mid;
}
ll ans=r;
check(r,n,s,m,x,y);
for (int i=0;i<ans;i++){
p[i]=ans1[i];
q[i]=ans2[i];
}
return ans;
}
/*
int32_t s[N],x[N],y[N],p[N],q[N];
int32_t main(){
ll n,m;
cin >> n;
for (int i=0;i<n;i++) cin >> s[i];
cin >> m;
for (int i=0;i<m;i++) cin >> x[i] >> y[i];
ll ans=findSwapPairs(n,s,m,x,y,p,q);
cout << ans << " ans " << endl;;
for (int i=0;i<ans;i++){
cout << ans1[i] << " " << ans2[i] << endl;
}
}
*/
/*
5
4 3 2 1 0
6
0 1
1 2
2 3
3 4
0 1
1 2
5
3 0 4 2 1
5
1 1
4 0
2 3
1 4
0 4
*/
Compilation message
sorting.cpp: In function 'll check(ll, int32_t, int32_t*, int32_t, int32_t*, int32_t*)':
sorting.cpp:23:27: error: 'par' was not declared in this scope
23 | for (int i=0;i<N;i++) par[i]=i;
| ^~~
sorting.cpp:64:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
64 | if (cng.size()>tool) return 0;
| ~~~~~~~~~~^~~~~
sorting.cpp:22:48: warning: unused parameter 'm' [-Wunused-parameter]
22 | ll check(ll tool,int32_t n,int32_t s[],int32_t m,int32_t x[],int32_t y[]){
| ~~~~~~~~^
