#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 6010;
pii arr[mxn];
int N,M;
int done = 0;
bitset<mxn> vis;
vector<pii> ans;
void act(vector<int> &perm,vector<int> &pos,int a,int b){
cerr<<"ACT "<<a<<','<<b<<endl;
cerr<<"PERM: ";for(auto &i:perm)cerr<<i<<' ';cerr<<endl;
cerr<<"POS: ";for(auto &i:pos)cerr<<i<<' ';cerr<<endl;
swap(perm[a],perm[b]);
swap(pos[perm[a]],pos[perm[b]]);
cerr<<"ACTED"<<a<<','<<b<<endl;
cerr<<"PERM: ";for(auto &i:perm)cerr<<i<<' ';cerr<<endl;
cerr<<"POS: ";for(auto &i:pos)cerr<<i<<' ';cerr<<endl;
return;
}
bool f(int len,vector<int> perm){
cerr<<"----------------------------------------"<<endl;
cerr<<"F "<<len<<" start!"<<endl;
vis.reset();
ans.clear();
vector<int> pos(N);
for(int i = 0;i<N;i++)pos[perm[i]] = i;
auto v = perm;
for(int i = 0;i<len;i++){
auto [a,b] = arr[i];
swap(v[a],v[b]);
}
vector<pii> need;
for(int i = 0;i<N;i++){
int now = i;
vis[now] = true;
int head = now;
now = v[now];
while(!vis[now]){
vis[now] = true;
need.push_back(pii(head,now));
now = v[now];
}
}
for(auto &i:v)cerr<<i<<' ';cerr<<endl;
if(need.size()>len)return false;
while(need.size()<len)need.push_back(pii(0,0));
cerr<<"NEED: "<<endl;for(auto &i:need)cerr<<i.fs<<' '<<i.sc<<endl;cerr<<endl;
for(int i = 0;i<len;i++){
auto [a,b] = arr[i];
act(perm,pos,a,b);
auto [c,d] = need[i];
ans.push_back(pii(pos[c],pos[d]));
act(perm,pos,pos[c],pos[d]);
}
for(int i = 0;i<N;i++)assert(perm[i] == i);
cerr<<"----------------------------------------"<<endl;
return true;
}
void construct(int P[],int Q[],int len){
assert(ans.size() == len);
for(int i = 0;i<len;i++){
P[i] = ans[i].fs,Q[i] = ans[i].sc;
}
return;
}
int findSwapPairs(int NN, int S[], int MM, int X[], int Y[], int P[], int Q[]) {
N = NN;M = MM;
for(int i = 0;i<M;i++)P[i] = Q[i] = 0;
vector<int> v(N);
for(int i = 0;i<N;i++){
v[i] = S[i];
}
for(int i = 0;i<M;i++)arr[i] = pii(X[i],Y[i]);
cerr<<"INIT!"<<endl;
for(int i = 0;i<M;i++){
if(f(i,v)){
construct(P,Q,i);
return i;
}
}
return -1;
assert(false);
}
