样例已过，第二个点WA求调
就是先求边双然后缩点，枚举割边

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<list>
#include<map>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
struct edge{
    int to,idx;
};
vector<edge> g[10005];
vector<int> t[10005];
int T,n,m;
int dfn[10005],low[10005],idx,from[10005],bridge[10005],vis[10005];
int c[10005],c_cnt,cnt[10005],tree[10005];
void tarjan(int u){
    dfn[u]=low[u]=++idx;
    for(int i=0;i<g[u].size();i++){
        edge e=g[u][i];
        if(from[u]==e.idx)continue;
        int v=e.to;
        if(!dfn[v]){
            from[v]=e.idx;
            tarjan(v);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])
                bridge[e.idx]=true;
        }else{
            low[u]=min(low[u],dfn[v]);
        }
    }
}
void dfsc(int u){
    c[u]=c_cnt;
    cnt[c[u]]++;
    for(int i=0;i<g[u].size();i++){
        edge e=g[u][i];
        if(bridge[e.idx]||vis[e.to])continue;
        vis[e.to]=true;
        dfsc(e.to);
    }
}
int dfs(int u){
    int sum=0;
    for(int i=0;i<t[u].size();i++){
        sum+=dfs(t[u][i]);
    }
    return tree[u]=cnt[u]+sum;
}
void init(){
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(from,0,sizeof(from));
    memset(bridge,0,sizeof(bridge));
    memset(c,0,sizeof(c));
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    memset(tree,0,sizeof(tree));
    idx=c_cnt=0;
    for(int i=0;i<=n;i++)g[i].clear(),t[i].clear();
}
int main(){
    cin>>T;
    while(T--){
        cin>>n>>m;
        init();
        for(int i=1,u,v;i<=m;i++){
            cin>>u>>v;
            g[u].push_back({v,i});
            g[v].push_back({u,i});
        }
        if(n==2&&g[1][0].to==2){
            cout<<0<<endl;
            continue;
        }
        tarjan(1);
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                c_cnt++;
                vis[i]=true;
                dfsc(i);
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=0;j<g[i].size();j++){
                edge e=g[i][j];
                if(bridge[e.idx]&&c[i]<c[e.to]){
                    t[c[i]].push_back(c[e.to]);
                }
            }
        }
        dfs(1);
        int ans=n*(n-1)/2;
        for(int i=1;i<=n;i++){
            for(int j=0;j<g[i].size();j++){
                edge e=g[i][j];
                if(bridge[e.idx]){
                    ans=min(ans,n*(n-1)/2-tree[c[e.to]]*(n-tree[c[e.to]]));
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}