#include "permgame.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
const int N=400;
vector<int>g[N];//initial graph/not P
vector<bool>vis(N);
vector<int>line;
vector<vector<int>>f;
vector<int>t;
int ans=0;
vector<array<int,3>>d;
int m,e,n;
vector<int>u,v,p;
vector<int>opt;
void find(int x){
line.pb(x);
vis[x]=true;
for(int y:g[x]){
if(!vis[y]){
find(y);
}
}
}
void dfs(int x){
vis[x]=true;
f.back().pb(x);
for(int y:g[x]){
if(!vis[y]){
dfs(y);
}
}
}
void go(){
fill(all(vis),false);
for(int i=0;i<n;i++){
g[i].clear();
}
f.clear();
for(int i=0;i<n;i++){
g[p[i]].pb(i);
g[i].pb(p[i]);
}
for(int i=0;i<n;i++){
if(!vis[i]){
f.pb({});
dfs(i);
}
}
sort(all(f),[&](vector<int>a,vector<int>b){
return (int)a.size()>(int)b.size();
});
}
void solve3(){
go();
for(int i=0;i<f.size();i++){
if(f[i].size()>=3&&opt[f[i].size()]>0){
int sz=f[i].size();
t[0]=f[i][d[sz][0]-1];
t[1]=f[i][d[sz][0]+d[sz][1]-1];
t[2]=f[i][d[sz][0]+d[sz][1]+d[sz][2]-1];
int j=Bob(t);
swap(p[t[u[j]]], p[t[v[j]]]);
solve3();
return;
}
}
return;
}
int Alice(int M, int E, vector<int> U, vector<int> V, int N_, vector<int> P) {
m=M,e=E,u=U,v=V,n=N_,p=P;
t.resize(m);
d.resize(n+5);
opt.resize(n+5);
if(m==2){
for(int i=0;i<n;i++){
if(p[i]!=i){
for(int j=i+1;j<n;j++){
if(p[j]==i){
t[0]=i;
t[1]=j;
int j=Bob(t);
swap(p[t[u[j]]], p[t[v[j]]]);
break;
}
}
}
}
return n;
}
for(int i=0;i<n;i++){
if(p[i]==i){
ans++;
}
}
if(e>m){
return ans;
}
int start=ans;
int deg=0;
for(int i=0;i<e;i++){
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
}
for(int i=0;i<m;i++){
deg=max(deg,(int)g[i].size());
}
if(deg>=3){
return ans;
}
find(0);
opt[1]=1;
for(int i=m;i<=n;i++){
for(int j=1;j<i;j++){
for(int l=1;l+j<i;l++){
int r=i-j-l;
int mn=min({opt[j]+opt[n-j],opt[l]+opt[n-l],opt[r]+opt[n-r]});
if(mn>opt[i]){
opt[i]=mn;
d[i]={j,l,r};
}
}
}
}
if(e==3){
solve3();
go();
ans=0;
for(int i=0;i<f.size();i++){
if(f[i].size()==1){
ans++;
}
}
return ans;
}
// vector<int>bef(n+5,0);
// vector<bool>dp(n+5,0);
// dp[0]=true;
// for(int x:v){
// for(int i=n;i>=0;i--){
// if(dp[i]){
// if(i+x<=n&&!dp[i+x]){
// dp[i+x]=true;
// bef[i+x]=x;
// }
// }
// }
// }
// if(!dp[n]){
// return ans;
// }
// vector<int>num;
// int cur=n;
// while(cur>0){
// num.pb(bef[cur]);
// cur-=bef[cur];
// }
// if(e==3){
// return ans;
// }
int play=n*10;
int mx=0;
bool reach=false;
while(play--){
fill(all(vis),false);
for(int i=0;i<n;i++){
g[i].clear();
}
f.clear();
for(int i=0;i<n;i++){
g[p[i]].pb(i);
g[i].pb(p[i]);
}
for(int i=0;i<n;i++){
if(!vis[i]){
f.pb({});
dfs(i);
}
}
sort(all(f),[&](vector<int>a,vector<int>b){
return (int)a.size()>(int)b.size();
});
vector<int>ord;
for(int i=0;i<f.size();i++){
for(int x:f[i]){
ord.pb(x);
}
}
for(int i=0;i<m;i++){
t[line[i]]=ord[i];
}
int j=Bob(t);
swap(p[t[u[j]]], p[t[v[j]]]);
{
int cnt=0;
for(int i=0;i<n;i++){
if(p[i]==i){
cnt++;
}
}
mx=max(mx,cnt);
if(cnt>=max(n-m+1,start)){
reach=true;
break;
}
}
}
if(!reach){
return max(n-m+1,start);
}
return max(n-m+1,start);
}
