#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define ROF(i,a,b) for(int i = a; i >= b; i--)
#define fi first
#define se second
#define pb push_back
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
if (N==1){
P[0] = 0;
Q[0] = 0;
return 1;
}
int pos[N];
FOR(i,0,N){
pos[S[i]] = i;
}
FOR(i,0,M){
if (X[i] != Y[i]){
swap(pos[S[X[i]]], pos[S[Y[i]]]);
swap(S[X[i]], S[Y[i]]);
}
if (i == N-2){
if (S[0] == 0){
P[i] = 0; Q[i] = 0;
}else{
P[i] = 0, Q[i] = 1;
}
if (P[i] != Q[i]){
swap(pos[S[P[i]]], pos[S[Q[i]]]);
swap(S[P[i]], S[Q[i]]);
}
break;
}
P[i] = pos[i+2];
Q[i] = i+2;
if (P[i] != Q[i]){
swap(pos[S[P[i]]], pos[S[Q[i]]]);
swap(S[P[i]], S[Q[i]]);
}
}
return N-1;
}
