#include "sorting.h"
#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else
#define dbg(...) 199958
#endif
#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
if(x>y){
x=y;
return true;
}
return false;
}
template<class T, class F>
bool chmax(T &x, F y){
if(x<y){
x=y;
return true;
}
return false;
}
double pass_time=0;
struct uf{
vc<int>par;
uf(int n):par(n,-1){}
int root(int a){
if(par[a]<0)return a;
return par[a]=root(par[a]);
}
int merge(int a,int b){
a=root(a),b=root(b);
if(a==b)return 0;
if(-par[a]<-par[b])swap(a,b);
par[a]+=par[b];
par[b]=a;
return 1;
}
};
vc<pair<int,int>>solve(int n,vc<int>s,int m,vc<int>x,vc<int>y){
auto judge=[&](int wj){
auto ns=s;
rep(i,wj){
swap(ns[x[i]],ns[y[i]]);
}
uf uf(n);
rep(i,n){
uf.merge(i,ns[i]);
}
int cnt=0;
rep(i,n)if(i==uf.root(i))cnt++;
if(n-cnt<=wj)return 1;
else return 0;
};
int ac=m,wa=0;
while(ac-wa>1){
int wj=ac+wa>>1;
if(judge(wj))ac=wj;
else wa=wj;
}
auto build=[&](int ac){
vc<pair<int,int>>ans;
uf uf(n);
auto ns=s;
rep(i,ac){
swap(ns[x[i]],ns[y[i]]);
}
rep(i,n)uf.merge(i,ns[i]);
vvc<int>gs(n);
rep(i,n){
gs[uf.root(i)].push_back(i);
}
vc<int>inv(n);
rep(i,n){
inv[ns[i]]=i;
}
auto SWAP=[&](int a,int b){
a=inv[a],b=inv[b];
swap(inv[ns[a]],inv[ns[b]]);
swap(ns[a],ns[b]);
};
dbg(gs);
rep(i,n){
REP(j,1,gs[i].size()){
ans.push_back({ns[gs[i][j]],gs[i][j]});
SWAP(ns[gs[i][j]],gs[i][j]);
}
}
dbg(ns);
while(ans.size()<ac)ans.push_back({0,0});
dbg(ans);
vc<int>now(n);
iota(all(now),0);
vc<int>now_inv(n);
rep(i,n)now_inv[i]=i;
//i番目のりんごが載っている皿
vc<int>now_on(n);
iota(all(now_on),0);
//i番目の皿が載せているリンゴ
vc<int>inv_on(n);
rep(i,n){
now_on[s[i]]=i;
}
inv_on=s;
rep(i,ac){
swap(now[x[i]],now[y[i]]);
swap(now_inv[now[x[i]]],now_inv[now[y[i]]]);
swap(now_on[ans[i].first],now_on[ans[i].second]);
ans[i].first=now[now_on[ans[i].first]];
ans[i].second=now[now_on[ans[i].second]];
}
dbg(ans);
return ans;
};
return build(ac);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
vc<int>s(N);
vc<int>x(M),y(M);
rep(i,N){
s[i]=S[i];
}
rep(i,M){
x[i]=X[i],y[i]=Y[i];
}
auto R=solve(N,s,M,x,y);
rep(i,R.size()){
P[i]=R[i].first;
Q[i]=R[i].second;
}
rep(i,R.size()){
swap(s[x[i]],s[y[i]]);
swap(s[R[i].first],s[R[i].second]);
}
rep(i,N)assert(s[i]==i);
return R.size();
}
#ifdef t9unkubj
namespace judge{
void run(){
int n;
cin>>n;
vc<int>s(n);
rep(i,n)cin>>s[i];
int m;
cin>>m;
vc<int>x(m),y(m);
rep(i,m)cin>>x[i]>>y[i];
auto R=(solve(n,s,m,x,y));
dbg("DON"s);
rep(i,R.size()){
swap(s[x[i]],s[y[i]]);
swap(s[R[i].first],s[R[i].second]);
}
dbg(s);
dbg(R);
}
};
int main(){judge::run();}
#endif
/*
8
3 5 7 0 1 2 4 6
10
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
*/
