#include <bits/stdc++.h>
using namespace std;
int Bob(vector<int>);
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
int n,m,a[405];
vector<int> g[405],cy;
pair<int,int> e[405];
vector<vector<int>> cs;
int d(){
bool v[405]={};
cs.clear();
for(int i=0;i<n;i++) if(!v[i]){
vector<int> c={i};
while(!v[c.back()]){
v[c.back()]=1;
c.pb(a[c.back()]);
}
c.pop_back();
cs.pb(c);
}
sort(all(cs),[](vector<int>&x,vector<int>&y){return sz(x)>sz(y);});
int r=n;
while(!cs.empty()&&sz(cs.back())==1){
r--;
cs.pop_back();
}
return r;
}
void s(vector<int> v){
vector<int> mv(m);
for(int i=0;i<m;i++) mv[cy[i]]=v[i];
int id=Bob(mv);
swap(a[mv[e[id].first]],a[mv[e[id].second]]);
}
void so(vector<int> v){
vector<int> r;
for(int i=0;i<m;i+=2) r.pb(v[i]);
for(int i=m-2;i>0;i-=2) r.pb(v[i]);
s(r);
}
void se(vector<int> v){
int s0=sz(v),c=0;
vector<int> r={c};
for(int i=0;i<m/2-1;i++){
if(c%(2*(s0-m)-2)==0) c+=s0-m;
else c++;
r.pb(c);
}
c++; r.pb(c);
c-=(s0-m); r.pb(c);
for(int i=0;i<m/2-2;i++){
if(c%(2*(s0-m)-2)==1) c-=s0-m;
else c--;
r.pb(c);
}
for(auto &x:r) x=v[x];
s(r);
}
int Alice(int M,int E,vector<int> U,vector<int> V,int N,vector<int> P){
n=N,m=M;
for(int i=0;i<n;i++) a[i]=P[i];
if(m==2){
d();
for(auto &c:cs) for(int i=1;i<sz(c);i++) Bob({c[0],c[i]});
return n;
}
for(int i=0;i<E;i++){
g[U[i]].pb(V[i]);
g[V[i]].pb(U[i]);
e[i]={U[i],V[i]};
}
int ans=0;
for(int i=0;i<n;i++) ans+=(a[i]==i);
bool bad=ans>=n-m+1;
for(int i=0;i<m;i++) if(sz(g[i])>=3) bad=1;
if(bad) return ans;
int r=0;
for(int i=0;i<m;i++) if(sz(g[i])==1) r=i;
cy={r};
for(int i=0;i<m-1;i++){
for(auto it:g[cy.back()]){
if(sz(cy)==1||cy[sz(cy)-2]!=it){
cy.pb(it);
break;
}
}
}
if(E+1==m||(m%2==0&&ans==n-m)){
while(d()>=m){
vector<int> v;
for(auto &c:cs) v.insert(v.end(),all(c));
v.resize(m);
s(v);
}
return n-m+1;
}
else if(m%2==1){
int goal=n-d();
int odd=0,tot=0,ext=0;
for(auto &c:cs){
if(sz(c)%2) odd++;
else tot+=sz(c);
}
for(auto &c:cs){
if(sz(c)%2&&sz(c)<m){
ext++;
tot+=sz(c);
}
}
goal+=odd-2*(ext/2);
while(d()>n-goal){
vector<int> v;
for(auto &c:cs) if(sz(c)%2){
if(sz(c)>m){ so(c); goto z; }
if(sz(c)==m){ s(c); goto z; }
}
for(auto &c:cs) if(!(sz(c)%2)) v.insert(v.end(),all(c));
while(sz(v)>m-1) v.pop_back();
for(auto &c:cs) if(sz(c)%2) v.insert(v.end(),all(c));
v.resize(m);
s(v);
z:;
}
return goal;
}
else{
while(d()>m+1){
int tot=0;
vector<int> v;
for(auto &c:cs) if(sz(c)==m){ s(c); goto a; }
for(auto &c:cs) if(sz(c)>=m+2){ se(c); goto a; }
for(auto &c:cs) if(sz(c)>2) tot+=sz(c);
if(tot<m+2) break;
for(auto &c:cs){
v.insert(v.end(),all(c));
if(sz(v)==sz(c)&&sz(v)>m-1) v.resize(m-1);
}
v.resize(m);
s(v);
a:;
}
while(d()>m+1){
vector<int> v;
for(auto &c:cs) if(sz(c)==m){ s(c); goto b; }
for(auto &c:cs) if(sz(c)>=2*m-1){ se(c); goto b; }
if(sz(cs)==1) break;
for(auto &c:cs){
v.insert(v.end(),all(c));
if(sz(v)==sz(c)&&sz(v)>m-1) v.resize(m-1);
}
v.resize(m);
s(v);
b:;
}
while(d()>m+1){
if(sz(cs[0])==m) s(cs[0]);
else if(sz(cs[0])>=m+2) se(cs[0]);
else{
vector<int> v;
for(auto &c:cs) v.insert(v.end(),all(c));
v.resize(m);
s(v);
}
}
return n-m-1;
}
}
