#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
// Yardımcı fonksiyon: R raundda sıralanıp sıralanamayacağını kontrol eder
bool check(int R, int N, vector<int> S, int M, int X[], int Y[], int P[], int Q[], bool fill_ans) {
vector<int> cur_S = S;
// Ermek'in hamlelerinden sonra hangi pozisyonun nereye gideceğini takip et
vector<int> pos(N);
iota(pos.begin(), pos.end(), 0);
for (int i = 0; i < R; i++) {
swap(pos[X[i]], pos[Y[i]]);
}
// Hedef: R hamle sonunda S[i] = i olmalı.
// Bunun için rüzgarın (Ermek) etkisini geri alarak başlangıçtaki 'ideal' hedefi bulalım.
vector<int> target_val(N);
for (int i = 0; i < N; i++) {
target_val[pos[i]] = i;
}
// Şu anki S dizisindeki değerlerin yerini tutan bir yardımcı dizi
vector<int> val_to_pos(N);
for (int i = 0; i < N; i++) {
val_to_pos[cur_S[i]] = i;
}
int swaps_needed = 0;
vector<pair<int, int>> aizhan_swaps;
for (int i = 0; i < N; i++) {
// Eğer i. pozisyonda olması gereken hedef değer orada değilse swap yap
if (cur_S[i] != target_val[i]) {
int v1 = cur_S[i];
int v2 = target_val[i];
int p1 = i;
int p2 = val_to_pos[v2];
aizhan_swaps.push_back({p1, p2});
swap(cur_S[p1], cur_S[p2]);
val_to_pos[v1] = p2;
val_to_pos[v2] = p1;
swaps_needed++;
}
}
if (swaps_needed > R) return false;
// Eğer kontrol fonksiyonu 'true' ise ve cevap isteniyorsa P ve Q dizilerini doldur
if (fill_ans) {
cur_S = S;
for (int i = 0; i < R; i++) {
// 1. Ermek swap yapar
swap(cur_S[X[i]], cur_S[Y[i]]);
// Aizhan'ın yapacağı swapları gerçek zamanlı takip etmeliyiz
// Çünkü Ermek her turda sayıların yerini değiştiriyor.
if (i < (int)aizhan_swaps.size()) {
// Aizhan'ın hedeflediği değerlerin o anki konumlarını bul
int val1 = S[aizhan_swaps[i].first];
int val2 = S[aizhan_swaps[i].second];
// Başlangıçtaki S üzerinde de takip yapmalıyız ki
// Aizhan'ın hangi değerleri seçtiğini bilelim
swap(S[aizhan_swaps[i].first], S[aizhan_swaps[i].second]);
// Güncel dizide bu değerlerin nerede olduğunu bul
int cur_p1 = -1, cur_p2 = -1;
for(int j=0; j<N; j++) {
if(cur_S[j] == val1) cur_p1 = j;
if(cur_S[j] == val2) cur_p2 = j;
}
P[i] = cur_p1;
Q[i] = cur_p2;
swap(cur_S[P[i]], cur_S[Q[i]]);
} else {
// İhtiyaç yoksa etkisiz swap
P[i] = 0;
Q[i] = 0;
}
}
}
return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
vector<int> initial_S(N);
for (int i = 0; i < N; i++) initial_S[i] = S[i];
int low = 0, high = M, ans = M;
// Minimum raundu bulmak için ikili arama
while (low <= high) {
int mid = (low + high) / 2;
if (check(mid, N, initial_S, M, X, Y, P, Q, false)) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
// Bulunan minimum raund için gerçek swap listesini oluştur
check(ans, N, initial_S, M, X, Y, P, Q, true);
return ans;
}
