#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 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];
}
bool h = check(m, S);
for(int i = 0; i < m; i++){
P[i] = ans[i].ff;
Q[i] = ans[i].ss;
}
return m;
}
