思路：考虑缩点，因为是无向图，所以双连通分量缩完点后是一棵树，我们去枚举删除每一条树边的答案，然后取最小值即可。

#include <bits/stdc++.h>using namespace std;
const int N = 3e5 + 5;
typedef long long ll;
typedef pair<int,int> pll;
typedef array<ll, 3> ar;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"int n,m;
vector<pll> e[N];
vector<int> e2[N];
vector<vector<int> > vdcc;
int dfsn[N],low[N],tot,b[N],sz[N];
stack<int> s;void add(int u,int v,int i)
{e[u].push_back({v,i});e[v].push_back({u,i});
}void tarjan(int x,int f)//tarjan 求边双连通分量
{dfsn[x]=low[x]=++tot,s.push(x);for(auto [u,i]: e[x]){if(!dfsn[u]){tarjan(u,i);low[x]=min(low[x],low[u]);}else if(f!=i) low[x]=min(low[x],dfsn[u]);}if(dfsn[x]==low[x]){vector<int> c;while(1){auto t=s.top();b[t]=vdcc.size();sz[vdcc.size()]++;c.push_back(t);s.pop();if(t==x) break;}vdcc.push_back(c);}
}void init()
{tot=0;for(int i=0;i<=n;i++){e[i].clear();e2[i].clear();dfsn[i]=b[i]=sz[i]=low[i]=0;}vdcc.clear();}ll ans=1e18;int dfs(int x,int f)
{ll sum=0;for(auto u: e2[x]){if(u!=f) sum+=dfs(u,x);}sum+=sz[x];ll res=n-sum;ans=min(ans,(sum)*(sum-1)/2+(res-1)*res/2);return sum;
}void solve()
{cin>>n>>m;init();ans=1e18;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;add(u,v,i);}for(int i=1;i<=n;i++){if(!dfsn[i]) tarjan(i,-1);}for(int i=1;i<=n;i++){for(auto [j,id]: e[i]){if(b[i]!=b[j]){e2[b[i]].push_back(b[j]);// e2[b[j]].push_back(b[i]);}}}dfs(b[1],-1);cout<<ans<<endl;
} int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;cin>>t;while(t--){solve();}system("pause");return 0;
}