#include "permgame.h"
#include <bits/stdc++.h>
using namespace std;
bool comp(const vector<int>&a, const vector<int>&b){
return a.size()<b.size();
}
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);
}
sort(ans.begin(),ans.end(),comp);
reverse(ans.begin(),ans.end());
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);
if(e==m-1){
int ans = 0;
int ansbest = n-m+1;
if(ansbest==n-1){
ansbest=n;
}
int sum = current[0].size();
for(vector<int>v:current){
if(v.size()==1){
ans++;
}
}
ans=max(ans,ansbest);
while(1){
///can use operation to merge 2 cycles as well.
current = cyc(p,n);
int curr = 0;
for(vector<int>v:current){
if(v.size()==1){
curr++;
}
}
if(curr>=ans)
break;
vector<int>mxv;
for(vector<int>v:current){
for(int i : v){
mxv.push_back(i);
}
}
///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]]]);
}
current = cyc(p,n);
int curr = 0;
for(vector<int>v:current){
if(v.size()==1){
curr++;
}
}
assert(curr>=ans);
return ans;
}
///e=m and one cycle of length m
int ans = 0;
current = cyc(p,n);
for(vector<int>v:current){
if(v.size()==1){
ans++;
}
}
int delta = 0;
for(vector<int>v:current){
if(v.size()==m){
delta++;
}
}
ans+=delta;
for(vector<int>V:current){
if(V.size()==m){
for(int i = 0;i<m;i++){
t[order[i]]=V[i];
}
int j = Bob(t);
swap(p[t[u[j]]], p[t[v[j]]]);
}
}
int curr = 0;
current=cyc(p,n);
for(vector<int>v:current){
if(v.size()==1){
curr++;
}
}
assert(curr==ans);
return ans;
}
