#include "permgame.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int Alice(int m, int e, std::vector<int> u, std::vector<int> v, int n, std::vector<int> p) {
int cur=0;
for(int i=0;i<n;i++){
if(p[i]==i) cur++;
}
if(e>m) return cur;
vector<vector<int>> adj(m);
for(int i=0;i<e;i++){
//cout<<u[i]<<' '<<v[i]<<'\n';
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
int st=0;
for(int i=0;i<m;i++){
if((int)adj[i].size()>2) return cur;
if((int)adj[i].size()==1) st=i;
}
vector<int> ord;
vector<bool> vis(m);
while(!vis[st]){
vis[st]=true;
ord.push_back(st);
int x=-1;
for(auto v:adj[st]){
if(!vis[v]){
x=v;
break;
}
}
if(x==-1) break;
st=x;
}
int best=0;
{
vector<bool> used(n);
for(int i=0;i<n;i++){
if(used[i]) continue;
vector<int> tmp;
int x=i;
while(!used[x]){
used[x]=true;
tmp.push_back(x);
x=p[x];
}
if((int)tmp.size()%2==1) best++;
}
}
while(true){
vector<vector<int>> cycle;
vector<bool> used(n);
for(int i=0;i<n;i++){
if(used[i]) continue;
vector<int> tmp;
int x=i;
while(!used[x]){
used[x]=true;
tmp.push_back(x);
x=p[x];
}
if((int)tmp.size()>1) cycle.push_back(tmp);
}
vector<vector<int>> cnt(n+1);
int mx=1;
for(int i=0;i<(int)cycle.size();i++){
cnt[(int)cycle[i].size()].push_back(i);
mx=max(mx,(int)cycle[i].size());
}
vector<int> res(m,-1);
if(e==m-1){
for(int i=0;i<m;i++){
if(cycle.empty()) break;
if(cycle.back().empty()) cycle.pop_back();
if(cycle.empty()) break;
res[i]=cycle.back().back();
cycle.back().pop_back();
}
}
else if(m==3 and e==3){
for(int i=3;i<=n;i+=2){
if(!cnt[i].empty()){
int id=cnt[i][0];
for(int t=0;t<3;t++){
res[ord[t]]=cycle[id][t];
}
}
}
}
else{
if((int)cnt[4].size()>=1){
int id=cnt[4][0];
for(int t=0;t<4;t++){
res[ord[t]]=cycle[id][t];
}
}
else if(mx>5){
int id=cnt[mx][0];
vector<int> ord4={0,1,5,4};
for(int t=0;t<4;t++){
res[ord[t]]=cycle[id][ord4[t]];
}
}
else if((int)cnt[2].size()>1){
int id1=cnt[2][0];
int id2=cnt[2][1];
for(int t=0;t<2;t++){
res[ord[t]]=cycle[id1][t];
}
for(int t=0;t<2;t++){
res[ord[t+2]]=cycle[id2][t];
}
}
else if((int)cnt[3].size()>1){
int id1=cnt[3][0];
int id2=cnt[3][1];
for(int t=0;t<2;t++){
res[ord[t]]=cycle[id1][t];
}
for(int t=0;t<2;t++){
res[ord[t+2]]=cycle[id2][t];
}
}
else if(n>=5 and (int)cnt[5].size()>=1){
int id1=cnt[5].back();
cnt[5].pop_back();
int id2=-1;
for(int i=2;i<=5;i++){
if((int)cnt[i].size()>=1){
id2=cnt[i][0];
break;
}
}
if(id2!=-1){
for(int t=0;t<2;t++){
res[ord[t]]=cycle[id1][t];
}
for(int t=0;t<2;t++){
res[ord[t+2]]=cycle[id2][t];
}
}
}
}
if(res.back()==-1) break;
int j=Bob(res);
swap(p[res[u[j]]],p[res[v[j]]]);
cur=0;
for(int i=0;i<n;i++){
if(p[i]==i) cur++;
}
}
if(m==3 and e==3) return best;
else return cur;
}
/*
3 3
0 1
1 2
2 0
10
8 2 7 6 1 5 0 9 3 4
*/
