#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) {
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> 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++) if ( p[i] == i ) {
in[i] = out[i] = i;
}
map<int, int> mp;
map<int, vector<int>> mpp;
vector<pair<int, int>> hi;
vector<map<int, int>> bye(n+132); // bye[sum] -> {idx, st};
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] ) {
vis[x] =1;
sz++;
mp[x] = idx;
mpp[idx].pb(x);
out[x] = p[x];
in[p[x]] = x;
x = p[x];
}
if ( (!c) || (sz<=m) ) {
hi.eb( sz, x );
bye[sz][idx] = x;
idx++;
sum += sz;
}
}
auto update = [&] (int u, int v) {
swap(in[u], in[v]);
out[in[u]] = u;
out[in[v]] = v;
bool ou =0, ov = 0;
if ( in[u] == out[u] ) ou = 1;
if ( in[v] == out[v] ) ov = 1;
if (ou&ov) {
sum-= 2;
bye[2].erase(mp[u]);
hi[mp[u]].f = 0;
return;
}
if (ou) {
sum--;
hi[mp[u]].s = v;
bye[hi[mp[u]].f].erase(mp[u]);
bye[--hi[mp[u]].f][mp[u]]=v;
return;
}
if (ov) {
sum--;
hi[mp[u]].s = u;
bye[hi[mp[u]].f].erase(mp[v]);
bye[--hi[mp[u]].f][mp[u]]=u;
return;
}
if ( mp[u] == mp[v] ) return;
int ns = hi[mp[u]].f+hi[mp[v]].f;
bye[hi[mp[u]].f].erase(mp[u]);
bye[hi[mp[v]].f].erase(mp[v]);
bye[ns][mp[u]] = u;
for (int& x : mpp[mp[v]]) {
mp[x] = mp[u];
mpp[mp[u]].pb(x);
}
hi[mp[u]].f = ns;
hi[mp[u]].s = u;
};
vector<int> ans;
vector<int> bb(m);
int op;
if (!c) {
op = max(cur, n-(sum-1) );
} else {
op = cur+ siz(bye[m]);
if (m==4&&e==4) op += siz(bye[2])/2;
}
while (true) {
ans.clear();
for (int i=2; i<siz(bye); i++) {
if (c && (siz(ans)<m) && (i>m)) break;
if (siz(ans)>=m) break;
if (siz(bye[i])==0) continue;
for (auto[idx, st] : bye[i]) {
if ( siz(ans)>= m ) break;
int ha = st;
ans.pb(st);
ha = out[st];
while (ha!=st) {
ans.pb(ha);
ha = out[ha];
}
}
}
if (siz(ans)<m) break;
for (int i=0; i<m; i++) bb[order[i]] = ans[i];
int x = Bob(bb);
int uu = rr[u[x]];
int vv = rr[v[x]];
update(ans[uu], ans[vv]);
}
return op;
}
