#include "permgame.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#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 cmp(const vector<int>& a, const vector<int>& b){
return a.size() > b.size();
}
int decomp(){
vector<bool> vis(n, false);
vect.clear();
for(int i = 0; i < n; i++){
if(!vis[i]){
vector<int> cur;
cur.pb(i);
vis[i] = true;
while(!vis[p[cur.back()]]){
vis[p[cur.back()]] = true;
cur.pb(p[cur.back()]);
}
vect.pb(cur);
}
}
sort(vect.begin(), vect.end(), cmp);
int res = 0;
while(!vect.empty() && vect.back().size() == 1){
res++;
vect.pop_back();
}
return n - res;
}
void bob(const vector<int>& t){
vector<int> res(m);
for(int i = 0; i < m; i++)
res[chain[i]] = t[i];
int id = Bob(res);
swap(p[res[edges[id].fi]], p[res[edges[id].se]]);
}
void odd(const vector<int>& t){
vector<int> res;
for(int i = 0; i < m; i += 2) res.pb(t[i]);
for(int i = m - 2; i > 0; i -= 2) res.pb(t[i]);
bob(res);
}
void even(const vector<int>& t){
int c = 0;
vector<int> res;
res.pb(t[0]);
for(int i = 0; i < m/2 - 1; i++){
if(c % (2*(t.size() - m) - 2)) c++;
else c += t.size() - m;
res.pb(t[c]);
}
c++;
res.pb(t[c]);
c -= t.size() - m;
res.pb(t[c]);
for(int i = 0; i < m/2 - 2; i++){
if(c % (2*(t.size() - m) - 2) == 1) c -= t.size() - m;
else c--;
res.pb(t[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.assign(n, {});
edges.resize(E);
if(m == 2){
decomp();
for(auto& c : vect)
for(int i = 1; i < (int)c.size(); i++)
Bob({c[0], c[i]});
return n;
}
for(int i = 0; i < E; i++){
graph[U[i]].pb(V[i]);
graph[V[i]].pb(U[i]);
edges[i] = {U[i], V[i]};
}
int ans = 0;
for(int i = 0; i < n; i++)
if(p[i] == i) ans++;
bool bad = false;
for(int i = 0; i < n; i++)
if(graph[i].size() >= 3) bad = true;
if(bad || ans >= n - m + 1)
return ans;
int start = 0;
for(int i = 0; i < n; i++)
if(graph[i].size() == 1)
start = i;
chain.clear();
chain.pb(start);
for(int i = 1; i < m; i++){
int last = chain.back();
if(chain.size() == 1 || graph[last][0] != chain[chain.size() - 2])
chain.pb(graph[last][0]);
else
chain.pb(graph[last][1]);
}
if(E == m - 1 || (!(m % 2) && ans == n - m)){
while(decomp() >= m){
vector<int> t;
for(auto& c : vect)
for(int x : c)
t.pb(x);
t.resize(m);
bob(t);
}
return n - m + 1;
}
if(m % 2){
int best = n - decomp();
int oddc = 0, sum = 0, del = 0;
for(auto& c : vect){
if(c.size() % 2) oddc++;
else sum += c.size();
}
for(auto& c : vect)
if(c.size() % 2 && sum < m)
sum += c.size(), del++;
best += oddc - del + (del % 2);
while(decomp() > n - best){
bool done = false;
for(auto& c : vect){
if(c.size() % 2){
if(c.size() > m){
odd(c);
done = true;
break;
}
if(c.size() == m){
bob(c);
done = true;
break;
}
}
}
if(!done){
vector<int> t;
for(auto& c : vect)
if(!(c.size() % 2))
for(int x : c) t.pb(x);
while((int)t.size() >= m) t.pop_back();
for(auto& c : vect)
if(c.size() % 2)
for(int x : c) t.pb(x);
t.resize(m);
bob(t);
}
}
return best;
}
while(decomp() > m + 1){
bool done = false;
for(auto& c : vect){
if(c.size() == m){
bob(c);
done = true;
break;
}
}
if(!done){
for(auto& c : vect){
if(c.size() >= m + 2){
even(c);
done = true;
break;
}
}
}
if(!done){
int sum = 0;
for(auto& c : vect)
if(c.size() >= 3) sum += c.size();
if(sum < m + 2) break;
vector<int> t;
for(auto& c : vect)
for(int i = 0; i < min((int)c.size(), m - 1); i++)
t.pb(c[i]);
t.resize(m);
bob(t);
}
}
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> t;
for(auto& c : vect)
for(int x : c) t.pb(x);
t.resize(m);
bob(t);
}
}
return n - m - 1;
}
