傳送門：https://www.luogu.com.cn/problem/P12542

題目大意：給定一個長為 $n$ 的排列和一張 $m$ 個點 $e$ 條邊的簡單連通圖。每次你可以在圖上每個點設置一個 $0～n?1$、兩兩不同的權值發給交互庫，交互庫會從圖中選擇一條邊，然后取出兩個端點上的權值，作為排列的兩個下標并進行交換。你可以隨時停止游戲。

你要先求出：在兩人的最優策略下，最終排列有多少個數歸位（即 $p[i]=i$），你要讓這個值最大化，交互庫要讓它最小化；并跟交互庫玩這個游戲，在 $3n$ 次操作內至少達到這個最優解。

數據范圍：$m\le n\le 400$。

Warning：本題思維復雜性較高，閱讀本題解之前請確保你處于大腦清醒的狀態。

先看一些簡單的 Case：

$m=2$

相當于你可以每次直接交換排列的兩個位置，那么就非常簡單了：你只需要貪心地每次把一個數歸位，至多 $n?1$ 次操作就可以讓整個排列全部歸位。

$e>m$

這是本題的第一個重要的觀察：為什么 $e>m$ 這個看起來很復雜的情況會放在第二個子任務而且只有 $6$ 分？

答：此時你無能為力，初始排列直接就是最優解。

為什么？我們直接證明一個更強的結論：只要圖中有 $\ge 3$ 度的點，你就沒有任何辦法了。

考慮圖中一個點 $x$ 被設置為權值 $t[x]$，如果選擇的一條邊與 $x$ 相連，什么情況下會對答案產生正的貢獻？只有兩種情況：將 $t[x]$ 這個數從別的位置交換回來；或者將 $p[t[x]]$ 這個數交換到了它正確的位置上去。

由于圖中所有的點權是兩兩不同的，因此上述兩種情況在一個點 $x$ 處都至多只有一條邊滿足。換句話說對于任意點而言，其相連的邊中至多只有兩條會讓答案增加。

因此，如果圖中存在 $\ge 3$ 度的點，交互庫就一定能選擇其一條鄰邊，使得操作之后答案嚴格不增。因此你的一切努力都是徒勞的。

那么問題來了：一張簡單連通圖沒有 $\ge 3$ 度的點，有哪幾種可能呢？只有兩種可能：鏈或環。

此外，容易看出當未歸位的點數不超過 $m?1$ 時，也無法更進一步了，因為將已經歸位的點加入圖中是沒有意義的。這作為平凡的情形，后文中將不再討論。

$e=m?1$

鏈的情況，我們開始進行一些真正接近題目本質的分析。

對于任意排列 $p$ 而言，可以建一張 $n$ 個點的圖，從每個點 $i$ 向 $p[i]$ 連邊，那么得到的一定形如若干個環。其中大小為 $1$ 的環表示已經歸位的點，我們不去管它；考慮其它的環我們怎么處理。

假設我們交換了兩個位置 $(i,j)$，實際上就是在圖中交換了這兩個點的出邊，對環結構的影響如下：

• 如果 $i,j$ 原本不在同一個環上，這次交換會將兩個環直接合并；

• 如果 $i,j$ 原本在同一個環上，假設環大小為 $p$，兩點在環上的距離為 $q$，則這次交換會將環拆分為兩個環，大小分別為 $q$ 和 $p?q$。

• 特別地，交換同一個環上相鄰的兩個位置會增加一個歸位的點（因為多了一個大小為 $1$ 的環）。
  
  然后我們有如下幾種操作：

• “強制歸位”：對于一個大小 $\ge m$ 的環，只需要順次選擇環上 $m$ 個相鄰的點，交互庫就必然要選擇兩個相鄰點交換使得多一個點歸位；

• “強制合并”：對于兩個大小加起來 $\ge m$ 的環，可以在一個環上順次選一些相鄰的點，再在另一個環上順次選一些相鄰的點，這樣交互庫就要么選擇一個環上的相鄰兩個點（這會讓一個點歸位）要么選擇兩個環上的點（這會合并這兩個環）。這一操作也可以推廣到多個環上，只要這些環大小之和 $\ge m$，就逼迫交互庫選擇其中相鄰兩個環進行合并。
  
  基于這兩種操作我們可以輕松解決鏈的情況：只需要先將所有環全都合并起來，再每次強制歸位一個點，就能操作到僅剩 $m?1$ 個點未歸位。

$e=m$

接下來是環的情況，在展開更詳細的分類討論之前，首先要說明環相對于鏈的一些不同之處。

• 對于“強制合并”影響不大，只不過在多個環時讓交互庫多了一種將首尾兩個環合并的選擇；

• 然而對于“強制歸位”的影響是關鍵的，因為這相當于在鏈的情形中增加了允許交互庫選擇鏈的首尾兩個點，這會導致環斷成兩段而不是恰好拆出一個點。因此如果你還想達到強制歸位的效果，就只能在大小恰好等于 $m$ 的環上執行。

• 那么遇到更大的環該怎么辦？為此我們必須開發出一種“強制拆分”操作：對于某個你想要的拆分距離 $d$，如果我們能在當前這個環上選取一系列點，使得（包括首尾在內，下同）相鄰兩個點的距離要么是 $1$ 要么是 $d$，那么交互庫為了不增加歸位的點數就必須選擇兩個間距為 $d$ 的點。如下圖就是 $d=2$ 的情形，分為 $m$ 是偶數/奇數兩種情形，對應的選取序列分別為 $0,2,4,\dots ,m?2,m?1,m?3,\dots ,1$ 和 $0,2,4,\dots ,m?1,m?2,m?4,\dots ,1$。需要注意的是，這樣的操作并不是我們隨心所欲的，需要根據 $m,d$ 和具體的環大小構造方案。
  
  再討論一些比較平凡的界：

• 對于剩余點數小于 $m$ 的情形，顯然沒法繼續操作了；

• 對于剩余點數恰為 $m$ 的情形，可以將所有環合并成一個之后歸位一次，得到剩余 $m?1$ 個點即為最優；

• 對于剩余點數恰為 $m+1$ 的情形，也沒法更進一步了，因為想要更進一步就必須先搞出大小為 $m$ 的環，但若果真如此那么剩下一個點已經自動歸位了，于是就矛盾了。

那么問題來了：當剩余點數更多時，是否總能操作到只剩 $m+1$ 個點？我們需要進一步分類討論。

$e=m=\text{奇數}$

先看 $m$ 是奇數的情形。基于上面的“強制拆分”操作，我們知道一個大小為 $m+2,m+4,\dots$ 的環總能通過每次拆下兩個點最終達到 $m$，從而可以進行一次歸位。也就是說任何大小至少為 $m$ 的奇環都能帶來 $1$ 的貢獻。

那么偶環呢？很遺憾，對于偶環我們又無能為力了。具體而言，考慮當前排列里的奇環總數（包括大小為 $1$ 的奇環），我們可以說明這個數量是無法增加的。

證明很簡單：如果想使得奇環的數量增加，唯有將一個偶環拆分成兩個奇環。然而如果我們將偶環進行間隔二染色，再選出 $m$ 個點填入圖中時，你會發現一定有相鄰兩個點是同色的。于是交互庫只要選這兩個點，就會將原先的偶環斷成兩個偶環。

基于上述分析，當前排列中奇環的數量就成了答案的上界。對于 $m=3$ 的情形，我們可以直接對所有的奇環每次進行 $?2$ 操作，直到變成 $3$ 之后進行一次歸位，就達到了這一最優解。

然而，當 $m$ 是更大的奇數時，可能面臨這樣的問題：有一系列小于 $m$ 的奇環，我們不能直接對其進行歸位操作，只能先與其他環合并；然而合并兩個奇環的操作是我們必須盡量避免的，因為這會使得答案上界 $?2$。

所以我們可以優先取出一個最大的奇環，首先考慮將其與所有的偶環合并，直到大小不小于 $m$ 為止；若合并上所有偶環之后大小仍然小于 $m$，我們就不得不從大到小選取若干個奇環進行合并，直到合并出不小于 $m$ 的奇環為止。

注意到一旦合并出了第一個不小于 $m$ 的奇環，后續就不再需要進行兩個奇環之間的合并了，因為對其進行拆分和歸位操作之后會得到大小為 $m?1$ 的偶環，在操作其他奇環時可以先將其與這個 $m?1$ 合并，以得到足夠大的奇環執行后續操作；操作最終又會得到一個 $m?1$ ，循環使用。

于是我們就完成了 $m$ 為奇數的情形，注意到操作次數顯然是夠用的。

$e=m=4$

來到了 $m$ 是偶數的情形，為了更加清晰，我們先看一下 $m=4$ 的簡單情形。

此時的理論上限是剩余 $5$ 個點，這是可以達到的，接下來將給出一系列操作：

• 對于 $4$ 元環可以歸位一個點；
• 對于 $\ge 6$ 的環，可以從中拆下來一個 $4$ 元環，選取點的序列為 $0,1,5,4$；
• 對于 $5$ 元環，不能直接進行操作，必須先與任意一個環合并；
• 對于兩個 $2$，可以合并成一個 $4$；
• 對于兩個 $3$，可以合并成一個 $6$；
• 盡量不要合并 $2$ 和 $3$，因為得到 $5$ 是不優的。

請注意上面的第二個操作，它可以擴展為一般的偶數 $m$：對于任意 $\ge \frac{3m}{2}$ 的環而言，都可以拆出一個 $m$，選取點的序列為 $0,1,2,\dots ,\frac{m}{2}?1,\frac{3m}{2}?1,\frac{3m}{2}?2,\dots ,m$。如下圖分別為 $m=4,6$ 的情形。

容易看出，只要按照上述操作序列依次執行，除合并 $2$ 和 $3$ 外，每 $3$ 步之內一定能進行一次歸位操作（可以自行驗證）。因此只要我們不去合并 $2$ 和 $3$（這在剩余點數多于 $5$ 時總是可以的），就能一直操作下去直到只剩 $5$ 個點為止，操作次數也是夠用的。

$e=m=\text{偶數}$

終于到了最復雜的情形，我們首先要看一下 $m$ 是一般的偶數相比 $m=4$ 時有哪些變化：最重要的變化是“強制拆分一個 $m$”只能適用于 $\ge \frac{3m}{2}$ 的環（至少我并沒有想到直接的適用于更小的環的拆分方案），因此我們需要重新設計將大小在 $m+2～\frac{3m}{2}?1$ 之間的環拆分成 $m$ 的方案。

• 對于大小為 $m+2,m+4,\dots$ 的環，仍然可以每次拆分一個 $2$ 出來，直到變成 $m$；
• 對于大小為 $m+3,m+5,\dots$ 的環，每次拆一個 $2$ 只能最終達到 $m+3$，再拆成 $m+1$ 是沒有意義的。因此我們必須要設計從 $m+3$ 直接拆出一個 $3$ 的策略。

具體方法是對 $m$ 按照 $\mathrm{mod}6$ 分類討論：

• $m\mathrm{mod}6=0:0,1,2,5,8,\dots ,m?1,m?2,m?3,m?6,m?5,m?8,m?9,\dots ,4,3$；
• $m\mathrm{mod}6=2:0,1,4,7,\dots ,m?1,m?2,m?3,m?6,m?5,m?8,\dots ,2,3$；
• $m\mathrm{mod}6=4:0,3,6,\dots ,m?1,m?2,m?3,m?6,m?5,m?8,\dots ,2,1$。

分類討論看著很繁瑣，其實本質都是同一種方案：先 $3$ 個 $3$ 個往前跳，再按照 $?1,?3,+1,?\mathrm{3...}$的模式往回跳。下圖中展示了 $m=6,8,10$ 的情形。另外，這種拆出 $3$ 個點的構造對于更大的環而言也是適用的。

再加上對小環的合并操作，我們便可以達到剩余 $m+1$ 的最優解。但操作次數是否滿足要求？

容易想到的操作序列如下：

• 如果存在一個 $m$，就進行一次歸位；
• 如果有兩個環大小之和為 $m$，合并之；
• 如果最大環 $\ge \frac{3m}{2}$，拆出一個 $m$；
• 如果最大環 $\ge m+2$ 但 $<\frac{3m}{2}$，拆出一個 $2$ 或 $3$；
• 如果最大的環 $=m+1$，就將其隨便合并一個環（例如次大環）；
• 如果最大的環 $<m$，就從大到小開始合并；例外是如果它與次大環加起來等于 $m+1$，就去考慮合并更小的環，除非別無選擇。

然而，這樣實際上并不能達到 $3n$ 的操作次數限制！考慮當前剩余的一系列環為 $m?1,2,2,\dots ,2$，將執行如下一系列操作：

• 將 $m?1$ 和 $2$ 合并為 $m+1$；
• 將 $m+1$ 和 $2$ 合并為 $m+3$；
• 將 $m+3$ 拆分為 $m$ 和 $3$；
• 對 $m$ 執行一次歸位變為 $m?1$；
• 將 $m?1$ 和 $3$ 合并為 $m+2$；
• 將 $m+2$ 拆分為 $m$ 和 $2$；
• 對 $m$ 執行一次歸位變為 $m?1$。

總共使用 $7$ 次操作進行了兩次歸位，除了 $2$ 環少了一個外其他均不變，可知這樣總的操作次數將達到 $3.5n$ 級別。

怎么辦？容易發現這一操作序列即使處理 $m=4$ 也是不行的，需要回看當時是怎樣避開這一問題的：現在相當于每次將 $3$ 和 $2$ 合并，然而這是我們不希望的，而當時是通過將兩個 $2$ 合并來避免了這一點。

這啟發我們如果場上有 $m?2$，就可以將其與 $2$ 合并從而直接得到 $m$。然而 $m?1$ 是容易得到的（$m$ 進行歸位一次之后就天然得到 $m?1$），但 $m?2$ 卻并不容易得到。

再回看 $m=4$ 的情形，發現可以通過操作制造 $2$：將兩個 $3$ 合并得到 $6$，再將 $6$ 拆分成 $4$ 和 $2$。

因此，對于更大的 $m$，如果場上有兩個 $m?1$，就可以先合并得到 $2m?2$，再通過一次拆分得到 $m$ 和 $m?2$。這也正是這道題的最后一個關鍵處。而兩個 $m?1$ 怎么得到？當然是從最初的一系列小環合并而來（或從更大的環上拆下來）。

總結上述的全過程，可以得到如下操作流程：

• 如果有 $m$，歸位之；
• 如果有兩個環大小之和為 $m$，合并之；
• 如果最大環 $\ge \frac{3m}{2}$，拆出一個 $m$；
• 如果最大環 $\ge m+2$ 但 $<\frac{3m}{2}$，拆出一個 $2$ 或 $3$；
• 如果最大環 $=m+1$，隨便找一個環（如次大環）合并；
• 如果最大環 $=m?1$ 且次大環 $=m?1$，合并二者；
• 如果最大環 $=m?1$ 且次大環 $=m?2$，找出第三大環：如果為 $2$，則與 $m?2$ 合并（避免與 $m?1$ 合并得到 $m+1$），否則與 $m?1$ 合并；
• 如果最大環 $=m?1$ 且次大環 $<m?2$，就從次大環開始順次合并（除非次大環與所有更小的環加起來已經不到 $m$ 了，就將最大環與次大環合并）；
• 如果最大環 $<m?1$，就從最大環開始順次合并。

分析總的操作次數：

我們要用 $3n$ 步歸位不超過 $n?m$ 個點，因此除了 “每 $3$ 步歸位一個點”以外，還有 $3m$ 步的冗余。

首先是最開始要合并出兩個 $m?1$，即使最初所有的環全是 $2$，這一步的額外開銷不會超過 $m$；

其次進行主操作流程，直至剩余 $2m$ 個點以前一直能維持“（均攤下來）每 $3$ 步歸位一個點”：只需額外分析當 $m?1$ 合并上一個不太大的環導致要進行一系列拆 $2,3$ 的操作，注意到這每一個 $2$ 或 $3$ 都能在后續步驟中省下來一步（例如 $m?2$ 和 $2$ 僅需兩步就能歸位一個點；$m?1,m?2,3$ 可以通過 $5$ 步歸位兩個點），因此之前拆出來的操作都能被均攤掉；

最后是剩余 $2m$ 個點之后，必須回滾到之前的操作流程。采用回先前 $3.5$ 步歸位一個點的流程，加上可能有額外的 $\frac{m}{2}$ 步拆分 $2,3$ 的操作，總的額外開銷不超過 $m$。

綜上，在“每 $3$ 步歸位一個點”以外，總的額外開銷不會超過 $2m$，于是本題終于徹底做完了。

#include <bits/stdc++.h>
using namespace std;
int Bob(std::vector<int> t);
int m,e,n,nwas,cnt;
vector<int> u,v,p;
vector<int> vis,deg;
vector<vector<int>> cycles;
vector<int> cyc_id, cyc_size, cyc_pos; // 一個點所在的環編號、大小以及它在環上的位置
vector<int> cyc_list,cyc_odd,cyc_even; // 按從大到小的順序排序后的所有環，后面兩個是所有的奇環和偶環
vector<int> dfn,map_g; // dfn是圖上節點編號的映射,map_g是dfn的逆
vector<vector<int>> edges; // 圖上的邊
vector<int> oper,oper_tmp; // 操作序列
void get_cycle(){ // 生成排列里所有的環cycles.clear();cyc_list.clear();cyc_odd.clear();cyc_even.clear();nwas = 0;memset(vis.data(),0,sizeof(int) * n);for(int i = 0;i < n;++i) if(!vis[i]){if(i == p[i]){ // 把已經歸位的去掉++nwas;continue;}vector<int> q; q.clear(); q.push_back(i); vis[i] = 1;for(int j = p[i];!vis[j];j = p[j]){q.push_back(j); vis[j] = 1;}int cycle_id = cycles.size(); // 當前環的編號cyc_list.push_back(cycle_id);for(int j = 0;j < q.size();++j){cyc_id[q[j]] = cycle_id; // 所在環編號cyc_size[q[j]] = q.size(); // 所在環大小cyc_pos[q[j]] = j; // 所在環上的位置}cycles.push_back(q);}// 按環長排序sort(cyc_list.begin(),cyc_list.end(),[=](int x,int y){return cycles[x].size() > cycles[y].size();}); // 將環按奇偶分類for(int i = 0;i < cyc_list.size();++i){int x = cyc_list[i];if(cycles[x].size() % 2) cyc_odd.push_back(x);else cyc_even.push_back(x);}
}
int nwdfn;
void dfs(int x){map_g[x] = nwdfn;dfn[nwdfn] = x;++nwdfn;for(int i = 0;i < edges[x].size();++i){int y = edges[x][i];if(map_g[y] != -1) continue;dfs(y);}
}
bool chk_deg(){oper.resize(m); memset(oper.data(),0,sizeof(int) * m);oper_tmp.resize(m); memset(oper_tmp.data(),0,sizeof(int) * m);deg.resize(m); memset(deg.data(),0,sizeof(int) * m);edges.resize(m);for(int i = 0;i < m;++i) edges[i].clear();for(int i = 0;i < e;++i){++deg[u[i]];++deg[v[i]];edges[u[i]].push_back(v[i]);edges[v[i]].push_back(u[i]);}for(int i = 0;i < m;++i) if(deg[i] >= 3) return 0;// 求出圖上點編號的映射關系map_g.resize(m); memset(map_g.data(),-1,sizeof(int) * m);dfn.resize(m); memset(dfn.data(),-1,sizeof(int) * m);nwdfn = 0;if(e == m - 1){ // 鏈的情況，要從1度點開始dfsfor(int i = 0;i < m;++i) if(deg[i] == 1){dfs(i);break;}}else dfs(0);return 1;
}int get_ans(){get_cycle();int ans = nwas;if(!chk_deg()) return ans; // 有3度及以上的點就GG了if(m == 2) return n; // 2個點if(ans > n - m) return ans; // ans已經很大了if(e == m - 1) return n - m + 1; // 鏈if(ans == n - m) return n - m + 1; // 剩下剛好m個點沒歸位if(m % 2 == 0) return n - m - 1; // 如果是偶數，則一定能剩下m+1個點int nwsz = 0;for(int i = 0;i < cycles.size();++i){if(cycles[i].size() % 2 == 0) nwsz += cycles[i].size(); // 累加上所有偶環的大小else ++ans; // 一個奇環意味著答案能+1}// 要從大到小檢查這些奇環，直到能合并出來一個>=m的為止bool fg = 0;for(int i = 0;i < cyc_odd.size() && nwsz < m;++i){int x = cyc_odd[i];if(fg){ // 這個奇環已經要被合并了nwsz += cycles[x].size();fg = 0;}else if(cycles[x].size() + nwsz < m){ // 要付出2的代價合并兩個奇環ans -= 2;nwsz += cycles[x].size();fg = 1;}else break;}return ans;
}
inline void add_node(int &nw, int x){oper[dfn[nw++]] = x;} // 注意要套一層dfn
inline void add_node_cyc(int &nw, int x,int j){add_node(nw,cycles[x][j]);
}
void get_m(int x){ // 從第x個環上切下長為m的一段來// 0 1 2 ... m/2-1 3m/2-1 3m/2-2 ... m+1 mint nw = 0;for(int i = 0;i < m / 2;++i) add_node_cyc(nw,x,i);for(int i = m / 2 - 1;i >= 0;--i) add_node_cyc(nw,x,i + m);
}
void get_3(int x){ // 從第x個環上切下長為3的一段來int j;int nw = 0;for(j = 0;(m - j) % 3 != 1;++j){ // 前面%3多出來的部分add_node_cyc(nw,x,j);}for(;j < m;j += 3){ // 間隔3個往前調add_node_cyc(nw,x,j);}int fg = -1;for(j = m - 2;j > 0;j -= 3 + fg){ // 從m-2開始，按照-1 -3 +1 -3 -1...的模式往回跳add_node_cyc(nw,x,j);add_node_cyc(nw,x,j + fg);fg *= -1;}
}
void get_2(int x){ // 從第x個環上切下長為2的一段來int nw = 0;// 1 3 5 ... m-1 m-2 m-4 ... 2 0// 正著走，間隔2個放一個for(int j = 1;j < m;j += 2){add_node_cyc(nw,x,j);}// 倒著走，間隔2個放一個for(int j = m - 2;j >= 0;j -= 2){add_node_cyc(nw,x,j);}
}
void gen_merge2(int x,int y){ // 合并兩個環，大小之和至少是mint nw = 0;for(int j = 0;nw + 1 < m && j < cycles[x].size();++j){ // 第一個環最多放m-1個點add_node_cyc(nw,x,j);}for(int j = 0;nw < m && j < cycles[y].size();++j){add_node_cyc(nw,y,j);}
}
void run(){ // 生成下一個操作序列，存在oper里if(m == 2){ // 把第一個i!=p[i]的強制歸位for(int i = 0;i < n;++i) if(p[i] != i){oper[0] = i;oper[1] = p[i];return;}}if(e == m - 1 || nwas == n - m){// 如果是鏈，或者剩余未歸位的總點數恰好等于m，可以直接這么干int nw = 0;// 從大到小遍歷所有的環，把點順次加進操作序列for(int i = 0;nw < m && i < cyc_list.size();++i){int x = cyc_list[i];for(int j = 0;nw < m && j < cycles[x].size();++j){add_node_cyc(nw,x,j);}}return;}int xx = -1;for(int i = 0;i < cycles.size();++i) if(cycles[i].size() == m){xx = i;break; // 找到了一個大小為m的環}if(xx != -1){ // 如果存在一個環剛好大小為m，就可以拆出來一個點int nw = 0;for(int j = 0;j < cycles[xx].size();++j){add_node_cyc(nw,xx,j);}return;}if(m % 2 == 1){ // 奇環// 由于還能繼續操作，一定還有奇環int x = cyc_odd[0];int nw = 0;if(cycles[x].size() > m){ // 第一個奇環足夠大// 0 2 4 ... m-1 m-2 m-4 ... 3 1// 正著走，間隔2個放一個for(int j = 0;j < m;j += 2){add_node_cyc(nw,x,j);}// 倒著走，間隔2個放一個for(int j = m - 2;j > 0;j -= 2){add_node_cyc(nw,x,j);}return;    }if(cycles[x].size() == m){ // 第一個奇環剛好是m，就強制拆出來一個點for(int j = 0;j < cycles[x].size();++j){add_node_cyc(nw,x,j);}return;}// 第一個環不夠大// 先把第一個環全都加進去for(int j = 0;nw < m && j < cycles[x].size();++j){add_node_cyc(nw,x,j);}// 然后把偶環加進去for(int i = 0;nw < m && i < cyc_even.size();++i){int x = cyc_even[i];for(int j = 0;nw < m && j < cycles[x].size();++j){add_node_cyc(nw,x,j);}}// 最后再加入其余的奇環for(int i = 1;nw < m && i < cyc_odd.size();++i){int x = cyc_odd[i];for(int j = 0;nw < m && j < cycles[x].size();++j){add_node_cyc(nw,x,j);}}}else{ // 偶環int x = cyc_list[0];int nw = 0;vector<int> sz;sz.resize(m);memset(sz.data(),-1,sizeof(int) * m);for(int i = 0;i < cycles.size();++i) if(cycles[i].size() < m){int nwsz = cycles[i].size();if(sz[m - nwsz] != -1){ // 這兩個環的大小之和剛好是m，合并之int y = sz[m - nwsz];gen_merge2(i,y);return;}sz[nwsz] = i;}if(cycles[x].size() == m - 1){ // 第一個環是m-1，特殊情況int y = cyc_list[1];if(cycles[y].size() == m - 1){ // 第二個環也是m-1，那么把他倆合并gen_merge2(x,y);return;}int tot_nxt = 0;for(int j = 1;j < cyc_list.size();++j) tot_nxt += cycles[cyc_list[j]].size();if(tot_nxt >= m){int z = cyc_list[2];if(cycles[y].size() + cycles[z].size() == m + 1){ // 這種情況讓z和x合并gen_merge2(x,y);}else{// 把剩下的都合并到y上for(int j = 1;nw < m && j < cyc_list.size();++j){int w = cyc_list[j];for(int k = 0;k < cycles[w].size() && nw < m;++k){add_node_cyc(nw,w,k);}}}return;}// tot_nxt<m的情況不歸這里考慮，回歸到普通情形    }if(cycles[x].size() < m){ // 第一個環不夠大// 從大到小遍歷所有的環，把點順次加進操作序列for(int i = 0;nw < m && i < cyc_list.size();++i){int x = cyc_list[i];for(int j = 0;nw < m && j < cycles[x].size();++j){add_node_cyc(nw,x,j);}}return;}if(cycles[x].size() == m + 1){ // 第一個環剛好是m+1，消除不了，要融合進去下一個環int y = cyc_list[1];gen_merge2(x,y);return;}if(cycles[x].size() >= 3 * m / 2){ // 第一個環特別大，允許拆出一個mget_m(x);return;}if(cycles[x].size() != m + 2 && cycles[x].size() != m + 4){ // 精細構造拆出一個3// update：每次拆下來兩個點會有問題，因為每次干掉一個點之后剩下的是m-1，就意味著還需要合并兩個2才行// 所以這里盡可能用了每次拆下來3個點的操作get_3(x);return;}// 第一個環足夠大而且不是m+3，可以每次拆下來兩個點get_2(x);}
}
int Alice(int _m, int _e, std::vector<int> _u, std::vector<int> _v, int _n, std::vector<int> _p){m = _m, e = _e, n = _n;u = _u, v = _v, p = _p;vis.resize(n); memset(vis.data(),0,sizeof(int) * n);cyc_id.resize(n); memset(cyc_id.data(),0,sizeof(int) * n);cyc_size.resize(n); memset(cyc_size.data(),0,sizeof(int) * n);cyc_pos.resize(n); memset(cyc_pos.data(),0,sizeof(int) * n);int final_ans = get_ans();cnt = 0;while(nwas < final_ans){++cnt;run();int res = Bob(oper);swap(p[oper[u[res]]], p[oper[v[res]]]);get_cycle(); // 重新生成環}return final_ans;
}