#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, in[H], out[H], m;
pi query[H], ans[H], a[H];
bool check(int t, int S[]){
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 < n; i++){
query[i].ff = X[i];
query[i].ss = Y[i];
}
bool h = check(n, S);
for(int i = 0; i < n; i++){
P[i] = ans[i].ff;
Q[i] = ans[i].ss;
}
return n;
}
