#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
const int len = 6e5+5;
int fin[len], arr[len], vis[len], plate[len], pos[len];
int n, m;
ii mov[len];
bool check(int x){
for (int i = 0; i < n; i++)
fin[i] = i;
for (int i = 0; i < x; i++)
swap(fin[mov[i].fi], fin[mov[i].se]);
for (int i = 0; i < n; i++)
plate[i] = fin[arr[i]], vis[i] = 0;
int rem = n;
for (int i = 0; i < n; i++){
if (vis[i]) continue;
int cur = plate[i];
vis[i] = 1;
while (cur != i)
vis[cur] = 1, cur = plate[cur];
rem--;
}
return (rem <= x);
}
int bs(){
int l = 0, r = m, ans;
while (l <= r){
int mid = (l+r)/2;
if (check(mid))
ans = mid, r = mid-1;
else
l = mid+1;
}
return ans;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
//freopen("CON", "w", stdin);
//printf("hello\n");
n = N, m = M;
for (int i = 0; i < n; i++)
arr[i] = S[i];
for (int i = 0; i < m; i++)
mov[i] = mp(X[i], Y[i]);
int k = bs();
check(k);
//printf("k = %d\n", k);
for (int i = 0; i < n; i++)
fin[i] = i, pos[i] = i;
/*for (int i = 0; i < n; i++)
printf("%d ", pos[i]);
printf("\n");*/
for (int i = 0, j = 0; i < k; i++){
//printf("i = %d\n", i);
int a = mov[i].fi, b = mov[i].se;
//printf("a = %d, b = %d\n", a, b);
swap(pos[fin[a]], pos[fin[b]]);
swap(fin[a], fin[b]);
/*for (int x = 0; x < n; x++)
printf("%d ", pos[x]);
printf("\n");*/
while (j < n && plate[j] == j)
j++;
if (j < n){
a = j, b = plate[j];
P[i] = pos[a];
Q[i] = pos[b];
plate[a] = plate[b];
plate[b] = b;
}
else{
P[i] = 0;
Q[i] = 0;
}
}
/*for (int i = 0; i < k; i++){
int a = mov[i].fi, b = mov[i].se;
swap(arr[a], arr[b]);
a = P[i], b = Q[i];
swap(arr[a], arr[b]);
for (int j = 0; j < n; j++)
printf("%d ", arr[j]);
printf("\n");
}*/
return k;
}
