#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;
} */
bool check(int t, int S[]){
int out[n], in[n];
for (int i = 0; i < n; ++i)
out[i] = in[i] = S[i];
for (int id = 0; id < t; ++id) {
int i = query[id].ff, j = query[id].ss;
swap(out[i], out[j]);
}
bool us[n];
memset(us, false, sizeof us);
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (us[i])
continue;
vector<int> ord;
int v = out[i];
while (v != i) {
ord.pb(v);
us[v] = true;
v = out[v];
}
ord.pb(v);
us[v] = true;
for (int j = sz(ord) - 1; j > 0; --j)
a[cnt++] = mp(ord[0], ord[j]);
}
if (cnt > t)return 0;
for (int i = 0; i < n; ++i)
pos[in[i]] = i;
for (int id = 0; id < cnt; ++id) {
int i = query[id].ff, j = query[id].ss;
swap(in[i], in[j]);
pos[in[i]] = i;
pos[in[j]] = j;
i = pos[a[id].ff]; j = pos[a[id].ss];
ans[id] = mp(i, j);
swap(in[i], in[j]);
pos[in[i]] = i;
pos[in[j]] = j;
}
while (cnt < t)
ans[cnt++] = mp(0, 0);
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 < m; i++){
query[i].ff = X[i];
query[i].ss = Y[i];
}
int l = -1, r = M;
while (r - l > 1) {
int m = (l + r) >> 1;
if (check(m, S)) {
r = m;
} else {
l = m;
}
}
check(r, S);
for(int i = 0; i < r; i++){
P[i] = ans[i].ff;
Q[i] = ans[i].ss;
}
return r;
}
