#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <int, int>
#define sz(x) (int)((x).size())
#include "sorting.h"
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const ll H = 1e6 + 11;
//ifstream in(".in");
//ofstream out(".out");
int pos[H], n, m;
pi query[H], ans[H], a[H];
bool check(int t, int S[]){
int in[n + 11], out[n + 11];
for(int i = 0; i < n; i++){
in[i] = out[i] = S[i];
}
for(int i = 0; i < t; i++){
swap(out[query[i].ff], out[query[i].ss]);
}
bool viz[n + 11];
memset(viz, 0, sizeof(viz));
int k = 0;
for(int i = 0; i < n; i++){
if(viz[i])continue;
vector<int>cur;
int v = out[i];
while(v != i){
cur.push_back(v);
v = out[v];
}
cur.push_back(v);
for(int j = sz(cur) - 1; j > 0; j--){
a[k++] = {cur[0], cur[j]};
}
for(auto it : cur)viz[it] = 1;
}
if(k > t)return 0;
for (int i = 0; i < n; ++i){
pos[in[i]] = i;
}
for(int i = 0; i < k; i++){
//His move
int x = query[i].ff, y = query[i].ss;
swap(in[x], in[y]);
pos[in[x]] = x;
pos[in[y]] = y;
//My move
x = pos[a[i].ff], y = pos[a[i].ss];
swap(in[x], in[y]);
pos[in[x]] = x;
pos[in[y]] = y;
ans[i] = {x, y};
}
while(k < t)ans[k++] = {0, 0};
return 1;
}
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 < m; i++){
query[i].first = X[i];
query[i].second = Y[i];
}
int lo = -1;
int hi = M;
while (lo + 1 < hi) {
int mid = (lo + hi) / 2;
if (check(mid, S)) {
hi = mid;
}
else {
lo = mid;
}
//toChange.clear();
}
check(hi, S);
//getAns(hi, S, N, X, Y);
for (int i = 0; i < hi; i++) {
P[i] = ans[i].first;
Q[i] = ans[i].second;
}
return hi;
}
