#include "permgame.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int n, m;
vector<int> p, chain;
vector<pii> edges;
vector<vector<int> > vect, graph;
bool custom(vector<int> a, vector<int> b){
return a.size()>b.size();
}
int decomp(){
vector<bool> visited(n, 0);
vect.clear();
for (int i=0; i<n; ++i)if (!visited[i]){
vector<int> temp(1, i);
visited[i]=1;
while (!visited[p[temp.back()]])visited[p[temp.back()]]=1, temp.pb(p[temp.back()]);
vect.pb(temp);
}
sort(vect.begin(), vect.end(), custom);
int res=0;
while (vect.size()&&vect.back().size()==1)++res, vect.pop_back();
return n-res;
}
void bob(vector<int> temp){
vector<int> res(m);
for (int i=0; i<m; ++i)res[chain[i]]=temp[i];
int id=Bob(res);
swap(p[res[edges[id].fi]], p[res[edges[id].se]]);
}
void odd(vector<int> temp){
vector<int> res;
for (int i=0; i<m; i+=2)res.pb(temp[i]);
for (int i=m-2; i>0; i-=2)res.pb(temp[i]);
bob(res);
}
void even(vector<int> temp){
int c=0;
vector<int> res(1, temp[0]);
for (int i=0; i<m/2-1; ++i){
if (c%(2*(temp.size()-m)-2))++c;
else c+=temp.size()-m;
res.pb(temp[c]);
}
++c;
res.pb(temp[c]);
c-=temp.size()-m;
res.pb(temp[c]);
for (int i=0; i<m/2-2; ++i){
if (c%(2*(temp.size()-m)-2)==1)c-=temp.size()-m;
else --c;
res.pb(temp[c]);
}
bob(res);
}
int Alice(int M, int e, vector<int> u, vector<int> v, int N, vector<int> P){
n=N, m=M;
p=P;
graph.resize(n);
if (m==2){
decomp();
for (auto c:vect)for (int i=1; i<c.size(); ++i)Bob({c[0], c[i]});
return n;
}
edges.resize(e);
for (int i=0; i<e; ++i){
graph[u[i]].pb(v[i]);
graph[v[i]].pb(u[i]);
edges[i]=mp(u[i], v[i]);
}
int ans=0;
bool die=0;
for (int i=0; i<n; ++i)if (i==p[i])++ans;
for (int i=0; i<n; ++i)if (graph[i].size()>=3)die=1;
if (die||ans>=n-m+1)return ans;
int start=0;
for (int i=0; i<n; ++i)if (graph[i].size()==1)start=i;
chain.resize(1, start);
for (int i=1; i<m; ++i){
if (chain.size()==1||graph[chain.back()][0]!=chain[chain.size()-2])chain.pb(graph[chain.back()][0]);
else chain.pb(graph[chain.back()][1]);
}
if (e==m-1||(!(m%2)&&ans==n-m)){
while (decomp()>=m){
vector<int> temp;
for (auto c:vect)for (auto a:c)temp.pb(a);
temp.resize(m);
bob(temp);
}
return n-m+1;
}
if (m%2){
int best=n-decomp(), o=0, sum=0, del=0;
for (auto c:vect){
if (c.size()%2)++o;
else sum+=c.size();
}
for (auto c:vect)if (c.size()%2&&sum<m)sum+=c.size(), ++del;
best+=o-del+del%2;
while (decomp()>n-best){
bool got=0;
for (auto c:vect)if (c.size()%2){
if (c.size()>m){
odd(c);
got=1;
break;
}
if (c.size()==m){
bob(c);
got=1;
break;
}
}
if (!got){
vector<int> temp;
for (auto c:vect)if (!(c.size()%2))for (auto a:c)temp.pb(a);
while (temp.size()>=m)temp.pop_back();
for (auto c:vect)if (c.size()%2)for (auto a:c)temp.pb(a);
temp.resize(m);
bob(temp);
}
}
return best;
}
while (decomp()>m+1){
bool got=0;
for (auto c:vect)if (c.size()==m){
got=1;
bob(c);
break;
}
if (!got)for (auto c:vect)if (c.size()>=m+2){
got=1;
even(c);
break;
}
if (!got){
int sum=0;
for (auto c:vect)if (c.size()>=3)sum+=c.size();
if (sum<m+2)break;
vector<int> temp;
for (auto c:vect)for (int i=0; i<min((int)c.size(), m-1); ++i)temp.pb(c[i]);
temp.resize(m);
bob(temp);
}
}
while (decomp()>m+1){
bool got=0;
for (auto c:vect)if (c.size()==m){
got=1;
bob(c);
break;
}
if (!got)for (auto c:vect)if (c.size()>=2*m-1){
got=1;
even(c);
break;
}
if (!got){
if (vect.size()==1)break;
vector<int> temp;
for (auto c:vect)for (int i=0; i<min((int)c.size(), m-1); ++i)temp.pb(c[i]);
temp.resize(m);
bob(temp);
}
}
while (decomp()>m+1){
if (vect[0].size()==m)bob(vect[0]);
else if (vect[0].size()>=m+2)even(vect[0]);
else{
vector<int> temp;
for (auto c:vect)for (auto a:c)temp.pb(a);
temp.resize(m);
bob(temp);
}
}
return n-m-1;
}
