#include "permgame.h"
#include <vector>
#include <utility>
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int Alice(int m, int e, std::vector<int> u, std::vector<int> v, int n, std::vector<int> p) {
assert(m==2||e>m||e==m-1);
vector<int> t(m);
if(m==2){
for(int i=0;i<n;i++){
if(p[i]==i)continue;
for(int j=i+1;j<n;j++){
if(p[j]==i){
t[0]=i;
t[1]=j;
int idx=Bob(t);
swap(p[t[u[idx]]],p[t[v[idx]]]);
}
}
}
return n;
}
else if(e>m){
int ans=0;
for(int i=0;i<n;i++){
if(p[i]==i)ans++;
}
return ans;
}
else if(e==m-1){\
//check if it's a line graph
vector<int> deg(m,0);
vector<int> adj[m];
for(int i=0;i<e;i++){
deg[u[i]]++;
deg[v[i]]++;
adj[u[i]].pb(v[i]);
adj[v[i]].pb(u[i]);
}
int cnt1=0;
for(int i=0;i<m;i++){
if(deg[i]==1)cnt1++;
}
if(cnt1>2){
int ans=0;
for(int i=0;i<n;i++){
if(p[i]==i)ans++;
}
return ans;
}
vector<int> line;
int start=1;
for(int i=0;i<m;i++){
if(deg[i]==1){
start=i;
break;
}
}
vector<int> visline(m,false);
queue<int> q;
q.push(start);
visline[start]=true;
while(!q.empty()){
int cur=q.front();
q.pop();
line.pb(cur);
for(auto next:adj[cur]){
if(visline[next])continue;
visline[next]=true;
q.push(next);
}
}
vector<int> vis(n,false);
int ans=0;
for(int i=0;i<n;i++){
if(vis[i])continue;
if(p[i]==i){
ans++;
continue;
}
vector<int> urutan;
for(int cur=i;!vis[cur];cur=p[cur]){
urutan.push_back(cur);
vis[cur]=true;
}
if((int)urutan.size()<m)continue;
while((int)urutan.size()>=m){
for(int i=0;i<m;i++){
t[line[i]]=urutan[i];
}
int idx=Bob(t);
swap(p[t[u[idx]]],p[t[v[idx]]]);
if(p[t[u[idx]]]==t[u[idx]]){
urutan.erase(find(urutan.begin(),urutan.end(),t[u[idx]]));
ans++;
}
if(p[t[v[idx]]]==t[v[idx]]){
urutan.erase(find(urutan.begin(),urutan.end(),t[v[idx]]));
ans++;
}
}
}
return ans;
}
return 100;
}
