#include"permgame.h"
#include<bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
#define ll long long
using namespace std;
int Alice(int M,int E,vector<int>U,vector<int>V,int N,vector<int>P){
int n=N,m=M,a[405],nc;
vector<int>al[405],ch,c[405];
pair<int,int>e[405];
auto decomp=[&](){
bool v[405]={};
nc=0;
for(int x=0;x<n;x++)if(!v[x]){
c[nc].clear(),c[nc].push_back(x);
while(!v[c[nc].back()])v[c[nc].back()]=1,c[nc].push_back(a[c[nc].back()]);
c[nc].pop_back(),nc++;
}
sort(c,c+nc,[](vector<int>a,vector<int>b){return a.size()>b.size();});
int r=n;
while(nc&&c[nc-1].size()==1)r--,nc--;
return r;
};
auto send=[&](vector<int>v){
vector<int>mv(m);
for(int x=0;x<m;x++)mv[ch[x]]=v[x];
int i=Bob(mv);
swap(a[mv[e[i].first]],a[mv[e[i].second]]);
};
auto so=[&](vector<int>v){
vector<int>r;
for(int x=0;x<m;x+=2)r.push_back(v[x]);
for(int x=m-2;x>0;x-=2)r.push_back(v[x]);
send(r);
};
auto se=[&](vector<int>v){
int s=v.size(),cu=0;
vector<int>r={cu};
for(int x=0;x<m/2-1;x++)cu%(2*(s-m)-2)==0?cu+=s-m:cu++,r.push_back(cu);
cu++,r.push_back(cu),cu-=(s-m),r.push_back(cu);
for(int x=0;x<m/2-2;x++)cu%(2*(s-m)-2)==1?cu-=s-m:cu--,r.push_back(cu);
for(auto&i:r)i=v[i];
send(r);
};
for(int x=0;x<n;x++)a[x]=P[x];
if(m==2){
decomp();
for(int i=0;i<nc;i++)for(int x=1;x<c[i].size();x++)Bob({c[i][0],c[i][x]});
return n;
}
for(int x=0;x<E;x++)al[U[x]].push_back(V[x]),al[V[x]].push_back(U[x]),e[x]={U[x],V[x]};
int ans=0,r=0;
for(int x=0;x<n;x++)ans+=(a[x]==x);
bool bad=ans>=n-m+1;
for(int x=0;x<m;x++)if(al[x].size()>=3)bad=1;
if(bad)return ans;
for(int x=0;x<m;x++)if(al[x].size()==1)r=x;
ch={r};
for(int x=0;x<m-1;x++)for(auto i:al[ch.back()])if(ch.size()==1||ch[ch.size()-2]!=i){ch.push_back(i);break;}
if(E+1==m||(m%2==0&&ans==n-m)){
while(decomp()>=m){
vector<int>v;
for(int i=0;i<nc;i++)v.insert(v.end(),c[i].begin(),c[i].end());
v.resize(m);
send(v);
}
return n-m+1;
}
else if(m&1){
int g=n-decomp(),od=0,sz=0,ex=0;
for(int i=0;i<nc;i++)c[i].size()%2==1?od++:sz+=c[i].size();
for(int i=0;i<nc;i++)if(c[i].size()%2==1&&sz<m)ex++,sz+=c[i].size();
g+=od-2*(ex/2);
while(decomp()>n-g){
vector<int>v;
bool done=0;
for(int i=0;i<nc&&!done;i++)if(c[i].size()%2==1){
if(c[i].size()>m)so(c[i]),done=1;
else if(c[i].size()==m)send(c[i]),done=1;
}
if(!done){
for(int i=0;i<nc;i++)if(c[i].size()%2==0)v.insert(v.end(),c[i].begin(),c[i].end());
while(v.size()>m-1)v.pop_back();
for(int i=0;i<nc;i++)if(c[i].size()%2==1)v.insert(v.end(),c[i].begin(),c[i].end());
v.resize(m);
send(v);
}
}
return g;
}
else{
while(decomp()>m+1){
int t=0;
vector<int>v;
bool done=0;
for(int i=0;i<nc&&!done;i++)if(c[i].size()==m)send(c[i]),done=1;
for(int i=0;i<nc&&!done;i++)if(c[i].size()>=m+2)se(c[i]),done=1;
if(!done){
for(int i=0;i<nc;i++)if(c[i].size()>2)t+=c[i].size();
if(t<m+2)break;
for(int i=0;i<nc;i++){
v.insert(v.end(),c[i].begin(),c[i].end());
if(v.size()==c[i].size()&&v.size()>m-1)v.resize(m-1);
}
v.resize(m),send(v);
}
}
while(decomp()>m+1){
vector<int>v;
bool done=0;
for(int i=0;i<nc&&!done;i++)if(c[i].size()==m)send(c[i]),done=1;
for(int i=0;i<nc&&!done;i++)if(c[i].size()>=2*m-1)se(c[i]),done=1;
if(!done){
if(nc==1)break;
for(int i=0;i<nc;i++){
v.insert(v.end(),c[i].begin(),c[i].end());
if(v.size()==c[i].size()&&v.size()>m-1)v.resize(m-1);
}
v.resize(m);
send(v);
}
}
while(decomp()>m+1){
if(c[0].size()==m)send(c[0]);
else if(c[0].size()>=m+2)se(c[0]);
else{
vector<int>v;
for(int i=0;i<nc;i++)v.insert(v.end(),c[i].begin(),c[i].end());
v.resize(m),send(v);
}
}
return n-m-1;
}
}
