#include "permgame.h"
#include <vector>
#include <utility>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define F(i,L,R) for (int i = L; i < R; i++)
#define FE(i,L,R) for (int i = L; i <= R; i++)
#define FF(i,L,R) for (int i = L; i > R; i--)
#define FFE(i,L,R) for (int i = L; i >= R; i--)
#define ms(a,x) memset(a,x,sizeof(a))
#define ALL(c) (c).begin(),(c).end()
#define SZ(a) sizeof(a)
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<char> vc;
typedef vector<vc> vvc;
int Alice(int m, int e, std::vector<int> u, std::vector<int> v, int n, std::vector<int> p) {
int cnt = 0;
for(int i = 0; i < n; i++){
if(p[i] == i) cnt++;
}
vi g[n];
for(int i = 0; i < e; i++){
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
}
int start_idx = -1;
for(int i = 0; i < m; i++){
if(g[i].size() > 2){
return cnt;
}
if(g[i].size() == 1 && start_idx == -1){
start_idx = i;
}
}
int cur_vertex = start_idx, last = -1;
vi atob(m), btoa(m);
for(int i = 0; i < m; i++){
atob[i] = cur_vertex;
btoa[cur_vertex] = i;
if(g[cur_vertex][0] != last){
last = cur_vertex;
cur_vertex = g[cur_vertex][0];
}else{
last = cur_vertex;
cur_vertex = g[cur_vertex][1];
}
}
vb vis(n, 0);
vi cycleof(n);
int cycle = 0;
for(int i = 0; i < n; i++){
if(p[i] != i && !vis[i]){
int cur = i;
do{
vis[cur] = 1;
cycleof[cur] = cycle;
cur = p[cur];
}while(cur != i);
cycle++;
}
}
vis.assign(n, 0);
vi t(m), ordered;
for(int i = 0; i < n; i++){
if(p[i] != i && !vis[i]){
int cur = i;
do{
/*for(int k = 0; k < ordered.size(); k++){
cout << ordered[k] << ' ';
}
cout << '\n';
for(int k = 0; k < n; k++){
cout << p[k] << ' ';
}
cout << '\n' << '\n';*/
if(ordered.size() == m){
for(int k = 0; k < m; k++){
t[atob[k]] = ordered[k]; // ordered: 0, 1, 2, 3, 4
}
int j = Bob(t);
if(btoa[u[j]] > btoa[v[j]]) swap(u[j], v[j]);
if(p[t[u[j]]] == t[v[j]]){
swap(p[t[u[j]]], p[t[v[j]]]);
ordered.erase(ordered.begin() + btoa[v[j]]);
}else{
int cycle_temp = -1, before = -1, value_temp = -1;
value_temp = ordered[btoa[v[j]]];
ordered.erase(ordered.begin() + btoa[v[j]]);
cycle_temp = cycleof[t[v[j]]];
before = btoa[u[j]];
swap(p[t[u[j]]], p[t[v[j]]]);
bool inserted = 0;
for(int k = before + 1; k < m; k++){
if(cycleof[ordered[k]] != cycle_temp){
ordered.insert(ordered.begin() + k, value_temp);
inserted = 1;
break;
}
}
if(!inserted) ordered.insert(ordered.end(), value_temp);
}
continue;
}
vis[cur] = 1;
ordered.pb(cur);
cur = p[cur];
}while(cur != i || ordered.size() == m);
}
}
return max(n - m + 1, cnt);
}
/*
5 4
0 1
1 2
2 3
3 4
10
1 2 3 4 0 6 7 8 9 5
*/
