題意：給出一個圓，順時針排布1~2*n，已知連了k條邊，問這個圓最好情況下有多少個線的交點，要求線與線之間不能有重復的連接點，也就是每個點只能被一條線連接

思路：

1.考慮沒有線的時候，那一定是i與i+n相連接，這一定是最多的連法

2.再考慮提前加了一條邊，那么一定是由這根線分割的兩邊相連，但是仔細想一下當兩邊數量不對等的時候，少的那一邊一定會連向多的一邊的中間

?如圖，這樣才是最多的，但是發現依舊是類似于i*i+n的構造方式

3.考慮繼續加邊，依舊會有這種感覺對嗎，因為這樣才會讓交點的數量多起來
考慮對自己能操作的邊進行交換，只會導致連的邊減少
但是對已有邊，不會改變性質
這是因為已有邊的貢獻是由min(上邊和下邊)決定的，單純的選兩條線改變交點，不會改變原有的兩個點處于上下邊的性質

?如圖，所以i與i+n這種構造模式，依舊是對已有邊的最佳處理
而且不會存在i與i+n在同一側的情況,i+k(某一邊的最小數量)<左側+右側/2，因此得證
對未填邊最大的處理方式，且一定滿足已有邊的需求

正確性來源參考CF1552C Maximize the Intersections 題解 - 洛谷專欄

至于本人？做的時候根本沒想這么多，試著試著就出來了，因為i與i+n的這種構造方式一定是對已有情況的最大，硬猜給猜出來了……

代碼：
這是自己寫過的代碼，有點臃腫，看著數據量直接強行暴力了，實際上很多步驟可以去掉……

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS                       \std::ios::sync_with_stdio(0); \std::cin.tie(0);              \std::cout.tie(0)const int N = 3e5 + 5;
const int INF = 1e18;
// const int MOD = 998244353;
// const int MOD=1e9+7;
// const int MOD=100003;
const int maxn=5e5+10;void solve(){int n,k;std::cin >> n >> k;std::vector<int> bz(2*(n+1));int cnt=n+1;std::vector<int> rec; for(int i=0;i<k;i++){int x,y;std::cin >> x >> y;int z=0;bz[x]=y;bz[y]=x;}int res=0;for(int p=1;p<=2*n;p++){std::vector<int> in,out;int now=0;int cnt=0;int i=p;while(cnt<2*n){if(!bz[i]){in.push_back(i);}i++;if(i==2*n+1) i=1;cnt++;}cnt=0;i=p;while(cnt<2*n){if(!bz[i]){out.push_back(i);}i--;if(i==0) i=2*n;cnt++;}for(int i=0,j=0;j<out.size()/2;i++,j++){bz[in[i]]=in[i+out.size()/2];bz[in[i+out.size()/2]]=in[i];}for(int i=1;i<=2*n;i++){if(bz[i]<i) continue;int nex=bz[i];for(int j=i+1;j<=bz[i];j++){if(bz[j]>bz[i]) now++;}}res=std::max(now,res);for(auto i : in){bz[i]=0;}}std::cout << res << '\n';}  signed main(){IOS;int t=1;std::cin >> t;while(t--){solve();}
}