#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
int n, m, x[600005], y[600005], s[600005];
vector<pi> swaps;
bool sortable(int limit){
//cerr << "STARTING " << limit << '\n';
swaps.clear();
vector<int> p(n), rev(n);
vector<int> fp(n);
vector<int> vis(n,0);
vector<pi> temp;
for (int i = 0; i < n; ++i){
p[i] = i;
}
for (int i = 0; i < limit; ++i){
swap(p[x[i]],p[y[i]]);
}
for (int i = 0; i < n; ++i){
fp[i] = s[p[i]];
}
for (int i = 0; i < n; ++i){
if (!vis[i]){
vis[i] = 1;
int idx = fp[i];
while (idx != i){
vis[idx] = 1;
temp.push_back(pi(idx,fp[idx]));
idx = fp[idx];
}
}
}
if ((int) temp.size() > limit) return false;
while ((int) temp.size() < limit) temp.push_back(pi(0,0));
for (int i = 0; i < n; ++i){
p[i] = s[i];
rev[s[i]] = i;
}
for (int i = 0; i < limit; ++i){
//cerr << x[i] << ' ' << y[i] << '\n';
swap(rev[p[x[i]]],rev[p[y[i]]]);
swap(p[x[i]],p[y[i]]);
//for (auto it : p) cerr << it << ' ';
//cerr << '\n';
int s1 = rev[temp[i].first], s2 = rev[temp[i].second];
//cerr << s1 << ' ' << s2 << '\n';
swaps.push_back(pi(s1,s2));
swap(rev[p[s1]],rev[p[s2]]);
swap(p[s1],p[s2]);
//for (auto it : p) cerr << it << ' ';
//cerr << '\n';
}
return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = N;
m = M;
for (int i = 0; i < N; ++i){
s[i] = S[i];
}
for (int i = 0; i < M; ++i){
x[i] = X[i];
y[i] = Y[i];
}
int ans = 0;
if (sortable(0)) return 0;
for (int i = 19; i >= 0; --i){
int test = ans + (1 << i);
if (test > M) continue;
if (!sortable(test)) ans = test;
}
ans++;
sortable(ans);
for (int i = 0; i < ans; ++i){
P[i] = swaps[i].first;
Q[i] = swaps[i].second;
}
return ans;
}
