#include "permgame.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>cyc(vector<int>p, int n){
bool vis[n];
fill(vis,vis+n,0);
vector<vector<int>>ans;
for(int i = 0;i<n;i++){
if(vis[i])
continue;
vis[i]=1;
int curr = p[i];
vector<int>curcyc;
curcyc.push_back(i);
while(curr!=i){
curcyc.push_back(curr);
vis[curr]=1;
curr=p[curr];
}
ans.push_back(curcyc);
}
return ans;
}
void dfs(int st, vector<int>g[], bool vis[], vector<int>&order){
order.push_back(st);
vis[st]=1;
for(int i : g[st]){
if(vis[i])
continue;
dfs(i,g,vis,order);
}
}
int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
vector<int> t(m);
vector<vector<int>>current = cyc(p,n);
vector<int>g[m];
for(int i = 0;i<e;i++){
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
for(int i = 0;i<m;i++){
if(g[i].size()>=3){
///bad
int ans = 0;
for(vector<int>v:current){
if(v.size()==1){
ans++;
}
}
return ans;
}
}
///need to find order of cyc.
vector<int>order;
bool vis[m];
fill(vis,vis+m,0);
dfs(0,g,vis,order);
while(1){
current = cyc(p,n);
int mxsiz = 0;
vector<int>mxv;
for(vector<int>v:current){
mxsiz=max(mxsiz,(int)v.size());
if(mxsiz==v.size()){
mxv=v;
}
}
if(mxsiz<m){
break;
}
///take m people from mxv
for(int i = 0;i<m;i++){
t[order[i]]=mxv[i];
}
int j = Bob(t);
swap(p[t[u[j]]], p[t[v[j]]]);
}
int ans = 0;
for(vector<int>v:current){
if(v.size()==1){
ans++;
}
}
return ans;
}
