#include <bits/stdc++.h>
#include "permgame.h"
using namespace std;
int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
// initial number of 1cycles
vector<bool> is_won(n);
int won_count = 0;
for(int i = 0; i < n; ++i) {
if(p[i] == i) {
is_won[i] = true;
++won_count;
}
}
// ordering the vertices of graph
vector<vector<int>> adj(m);
for(int i = 0; i < e; ++i) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
vector<int> chain;
int start = 0;
for(int i = 0; i < m; ++i) {
if((int)adj[i].size() == 1) {
start = i;
break;
}
}
vector<bool> visited(m);
queue<int> bfs;
bfs.push(start);
while(!bfs.empty()) {
int i = bfs.front();
bfs.pop();
if(visited[i]) continue;
visited[i] = true;
chain.push_back(i);
for(int j: adj[i]) bfs.push(j);
}
int win_target = (m == 2) ? n : n - m + 1;
while(won_count < win_target) {
vector<bool> is_free(is_won);
vector<int> t(m);
int chain_idx = 0;
// embed the chain into the permutation cycle graph
for(int i = 0; i < n; ++i) {
if(!is_free[i]) continue;
is_free[i] = false;
t[chain[chain_idx++]] = i;
int perm_cycle_idx = p[i];
while(perm_cycle_idx != i && chain_idx < m) {
is_free[perm_cycle_idx] = false;
t[chain[chain_idx++]] = perm_cycle_idx;
perm_cycle_idx = p[perm_cycle_idx];
}
if(chain_idx == m) break;
}
int b = Bob(t);
int s1 = t[u[b]], s2 = t[u[b]];
swap(p[s1], p[s2]); // p[s2] goes to index s1, p[s1] goes to index s2
if(s1 == p[s1]) {
is_won[s1] = true;
++won_count;
}
if(s2 == p[s2]) {
is_won[s2] = true;
++won_count;
}
}
return win_target;
// for (int i = 0; i < m; i++){
// t[i] = i;
// }
// int j = Bob(t);
// swap(p[t[u[j]]], p[t[v[j]]]);
// return 42;
}
