#include "permgame.h"
#ifdef Asaad
#include "cp.h"
#define debug(...) _dbg_many(#__VA_ARGS__, __VA_ARGS__)
#define here cerr << "LINE " << __LINE__ << "\n"
#else
#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
#define debug(...)
#define here
#endif
#define ll long long
//#define int long long
#define all(x) x.begin(), x.end()
#define siz(x) ((int)x.size())
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define f first
#define s second
#define eb emplace_back
#define pb push_back
const int mod = 1e9+7;
const int N = 200009;
const long long inf = 1e18+12309138;
double eps = 1e-9;
int Alice(int m, int e, std::vector<int> u, std::vector<int> v, int n, std::vector<int> p) {
int mod = m-1;
vector<vector<int>> adj(m);
for (int i=0; i<e; i++) {
adj[u[i]].pb(v[i]);
adj[v[i]].pb(u[i]);
}
int cur = 0;
for (int i=0; i<n; i++) cur+= (p[i]==i);
bool ok = 1;
bool c = 0;
for (int i=0; i<m; i++) ok&=( siz(adj[i]) < 3 );
if (!ok) return cur;
int st = -1;
for (int i=0; i<m; i++) if ( siz(adj[i]) == 1 ) st = i;
if (st==-1) {
st = 0;
c =1;
}
vector<int> order, vis(n, 0), rr(m);
vector<int> cr(n);
vector<int> in(n), out(n);
function<void(int)> dfs = [&] (int u) {
vis[u]=1 ;
order.pb(u);
for (int& v : adj[u]) if (!vis[v]) dfs(v);
};
dfs(st);
fill(all(vis), 0);
for (int i=0; i<m; i++) rr[order[i]] = i;
for (int i=0; i<n; i++) cr[p[i]] = i;
for (int i=0; i<n; i++) if ( p[i] == i ) {
in[i] = out[i] = i;
vis[i] = 1;
}
map<int, int> mp;
map<int, set<int>> mpp;
vector<pair<int, int>> hi;
vector<map<int, int>> bye(m+3); // bye[sum] -> {idx, st};
bool ch;
int idx = 0;
int sum = 0;
for (int i=0; i<n; i++) {
if (vis[i]) continue;
int sz = 0;
int x = p[i];
while ( !vis[x] ) {
debug(idx, x);
vis[x] =1;
sz++;
mp[x] = idx;
mpp[idx].insert(x);
out[x] = p[x];
in[p[x]] = x;
x =p[x];
}
hi.eb( sz, x );
bye[sz%mod][idx] = x;
idx++;
sum += sz;
}
auto update = [&] (int u, int v) {
swap(in[u], in[v]);
swap(cr[u], cr[v]);
out[in[u]] = u;
out[in[v]] = v;
bool ou =0, ov = 0;
if ( in[u] == out[u] && in[u]==u) ou = 1;
if ( in[v] == out[v] && in[v]==v) ov = 1;
if (ou&ov) {
sum-= 2;
bye[2%mod].erase(mp[u]);
hi[mp[u]].f = 0;
mpp[mp[u]].clear();
return;
}
if (ou) {
sum--;
hi[mp[u]].s = v;
bye[hi[mp[u]].f%mod].erase(mp[u]);
bye[(mod+(--hi[mp[u]].f))%mod][mp[u]]=v;
mpp[mp[u]].erase(u);
return;
}
if (ov) {
sum--;
hi[mp[v]].s = u;
bye[hi[mp[v]].f%mod].erase(mp[v]);
bye[(mod+(--hi[mp[v]].f))%mod][mp[v]]=u;
mpp[mp[v]].erase(v);
return;
}
if ( mp[u] == mp[v] ) {
int nu = 1, nv = 1;
int uu = out[u], vv = out[v];
while ( uu != u ) {
nu++;
uu = out[uu];
}
while (vv != v) {
nv++;
vv = out[vv];
}
if (nu != mod) swap(u, v);
bye[hi[mp[v]].f%mod].erase(mp[v]);
hi[mp[v]].f-= mod;
hi[mp[v]].s = v;
bye[hi[mp[v]].f%mod][mp[u]] = v;
uu = out[uu];
/*
mpp[mp[v]].erase(uu);
while (uu != u) {
mpp[mp[v]].erase(uu);
uu = out[uu];
}*/
return;
}
int ns = hi[mp[u]].f+hi[mp[v]].f;
bye[hi[mp[u]].f%mod].erase(mp[u]);
bye[hi[mp[v]].f%mod].erase(mp[v]);
bye[ns%mod][mp[u]] = u;
for (auto& x : mpp[mp[v]]) {
mp[x] = mp[u];
mpp[mp[u]].insert(x);
}
hi[mp[u]].f = ns;
hi[mp[u]].s = u;
};
vector<int> ans;
vector<int> bb(m);
auto bob = [&] () {
for (int i=0; i<m; i++) bb[order[i]] = cr[ans[i]];
int x = Bob(bb);
int uu = rr[u[x]];
int vv = rr[v[x]];
update(ans[uu], ans[vv]);
ch = 1;
};
int op;
if (e==m-1) {
op = max(cur, n-mod );
if (m==2) op = n;
while (sum>=m) {
ans.clear();
for (auto& a : bye) {
if (siz(ans)>=m) break;
for (auto& [id, st] : a) {
if ( siz(ans)>=m ) break;
int tmp = out[st];
ans.pb(st);
while (tmp != st) {
ans.pb(tmp);
tmp = out[tmp];
if (siz(ans)>=m) break;
}
}
}
bob();
}
return op;
}
op = cur+siz(bye[1]);
for (int i=2; i<mod; i++) {
if ( i > mod-i+1 ) break;
if (i==mod-i+1) op+= siz(bye[i])/2;
else op+= min( siz(bye[i]), siz(bye[mod-i+1]) );
}
auto merge = [&] (int u, int v) {
ans.clear();
int tmp = out[u];
ans.pb(u);
while (tmp != u) {
if ( siz(ans) == mod ) break;
ans.pb(tmp);
tmp = out[tmp];
}
ans.pb(v);
tmp = out[v];
while (tmp != v) {
if ( siz(ans) == m ) break;
ans.pb(tmp);
tmp = out[tmp];
}
};
ch = 1;
while (ch) {
ch = 0;
for (int i=2; i<mod; i++) {
if ( i > mod-i+1 ) break;
if (i==mod-i+1) {
while (true) {
if ( bye[i].empty() ) break;
auto ut = bye[i].begin();
auto vt = prev(bye[i].end());
if (ut == vt) break;
merge(ut->s, vt->s);
bob();
}
}
else {
while (true) {
if ( bye[i].empty() || bye[mod-i+1].empty() ) break;
auto ut = bye[i].begin();
auto vt = bye[mod-i+1].begin();
merge(ut->s, vt->s);
bob();
}
}
}
while (true) {
ans.clear();
if (siz(ans)>=m) break;
for (auto& [id, st] : bye[1]) {
if ( siz(ans)>=m ) break;
int tmp = out[st];
ans.pb(st);
while (tmp != st) {
ans.pb(tmp);
tmp = out[tmp];
if (siz(ans)>=m) break;
}
}
if (siz(ans)<m) break;
bob();
}
}
for (int i=2; i<mod; i++) {
if ( i > mod-i+1 ) break;
if (i==mod-i+1) {
while (true) {
if ( bye[i].empty() ) break;
auto ut = bye[i].begin();
auto vt = prev(bye[i].end());
if (ut == vt) break;
merge(ut->s, vt->s);
bob();
}
}
else {
while (true) {
if ( bye[i].empty() || bye[mod-i+1].empty() ) break;
auto ut = bye[i].begin();
auto vt = bye[mod-i+1].begin();
merge(ut->s, vt->s);
bob();
}
}
}
while (true) {
ans.clear();
if (siz(ans)>=m) break;
for (auto& [id, st] : bye[1]) {
if ( siz(ans)>=m ) break;
int tmp = out[st];
ans.pb(st);
while (tmp != st) {
ans.pb(tmp);
tmp = out[tmp];
if (siz(ans)>=m) break;
}
}
if (siz(ans)<m) break;
bob();
}
return op;
}
