我的做法是，考虑建立圆方树，方点的权值是点双的大小，圆点的权值是-1，计算每个节点的带权深度，然后枚举LCA求解。

#include <bits/stdc++.h>
using namespace std;
int n,m;
struct edge{
	int to,e;
};
const int maxn=1e6+10;
int w[maxn],sum[maxn];
vector<edge> vec[maxn];
int cnt,dfn[maxn],low[maxn];
vector<int> tree[maxn];
int tot=0;
stack <int> s;
void tarjan(int k,int e){
	low[k]=dfn[k]=++cnt;
	s.push(k);
	int son=0;
	for(auto to:vec[k]){
		int t=to.to,num=to.e;
		if(e==(num^1)) continue;
		if(!dfn[t]){
			son++;
			tarjan(t,num),low[k]=min(low[k],low[t]);
			if(low[t]>=dfn[k]){
				tot++;
				tree[k].push_back(tot);
				tree[tot].push_back(k);
				w[k]=-1;
				w[tot]++;
				while(s.top()!=t){
					w[tot]++;
					w[s.top()]=-1;
					tree[s.top()].push_back(tot);
					tree[tot].push_back(s.top());
					s.pop();
				}
				w[s.top()]=-1;
				tree[s.top()].push_back(tot);
				tree[tot].push_back(s.top());
				s.pop();
			}
		} 
		else low[k]=min(low[k],dfn[t]);
	}
}
//考虑lca(a,b),只有两个儿子的情况，s在左f在右，s可以是左边的所有节点，f是右边的所有节点
//dis a,b=dep[a]+dep[b]-dep[lca(a,b)] -dep[fa[lca(a,b)]]
//sum(dis(a,b)) a,b
//=sum(dep[a]+dep[b]-dep[t]-dep[fa[t]]);
//
//对于多个儿子的情况，合并每个儿子即可。
int siz[maxn],top[maxn],fa[maxn],son[maxn],dep[maxn];
long long depsum[maxn];
void dfs1(int x,int f){
	siz[x]=1;fa[x]=f;dep[x]=dep[f]+w[x];
	depsum[x]=dep[x];
	for(auto to:tree[x]){
		if(to==f) continue;
		dfs1(to,x);
		siz[x]+=siz[to];
		if(siz[to]>siz[son[x]]) son[x]=to;
		depsum[x]+=depsum[to];
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m;
	tot=n;
	for(int i=1;i<=m;i++){
		int u,v;
		cin >> u >> v;
		vec[u].push_back({v,2*i});
		vec[v].push_back({u,2*i+1});
	}
	for(int i=1;i<=tot;i++){
		if(!dfn[i]){
			tarjan(i,0);
			dfs1(i,0);
		}
	}
	
	long long ans=0;
    for(int i=1;i<=tot;i++){
		vector<int> v;
		for(auto to:tree[i]){
			if(to!=fa[i]){
				v.push_back(to);
			}
			
		}
		int siza=0,sizb=0,sumdepa=0,sumdepb=0;
		if(v.size()==1) {
			ans+=depsum[v[0]];
			continue;
		}
		if(!v.size()){
			ans+=dep[i];
			continue ;
		}
		for(int j=0;j<v.size()-1;j++){//怀疑这里统计答案出错，求助。
			if(j==0){
				siza=siz[v[j]];
				sumdepa=depsum[j];
			}
			sizb=siz[v[j+1]];
			sumdepb=depsum[j+1];
			ans+=siza*sumdepb+sizb*sumdepa-siza*sizb*(dep[i]+dep[fa[i]]);
			sumdepa+=sumdepb;
			siza+=sizb;
	    }
	}
	
	cout << ans << endl;
}