建立圆方树，考虑所有路径，发现路径上原来的点双(现在的方点)里的点都可以做中间点。但是路径上被方点夹着的圆点被计重了，要扣掉；枚举的两个端点也被算进去了，要扣掉。所以直接将方点权值设为点双大小，圆点权值设为-1，所有圆点间路径权值和的和即为答案
注意图可能不连通，草(汉语)
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=;
int n,m,r,c,t1,t2,cnt,Cnt,tot,top; long long sum,ans;
int dfn[N],low[N],col[N],isc[N],stk[N],siz[N],dis[N];
int p[N],noww[M],goal[M],P[N],Noww[M],Goal[M],val[N];
vector<int> ve[N];
void Link(int f,int t)
{
noww[++cnt]=p[f];
goal[cnt]=t,p[f]=cnt;
noww[++cnt]=p[t];
goal[cnt]=f,p[t]=cnt;
}
void Linka(int f,int t)
{
Noww[++Cnt]=P[f];
Goal[Cnt]=t,P[f]=Cnt;
Noww[++Cnt]=P[t];
Goal[Cnt]=f,P[t]=Cnt;
}
void Tarjan_PBC(int nde)
{
int tep=; stk[++top]=nde;
dfn[nde]=low[nde]=++tot;
for(int i=p[nde];i;i=noww[i])
if(!dfn[goal[i]])
{
Tarjan_PBC(goal[i]);
low[nde]=min(low[nde],low[goal[i]]);
if(dfn[nde]<=low[goal[i]])
{
if(nde!=r||++tep>) isc[nde]=true;
int tmp; c++;
do
{
tmp=stk[top--],col[tmp]=c;
ve[c].push_back(tmp);
}while(tmp!=goal[i]);
ve[c].push_back(nde);
}
}
else low[nde]=min(low[nde],dfn[goal[i]]);
}
void DFS(int nde,int fth)
{
if(nde<=n) siz[nde]=;
for(int i=P[nde];i;i=Noww[i])
if(Goal[i]!=fth) DFS(Goal[i],nde),siz[nde]+=siz[Goal[i]];
}
void Getans(int nde,int fth)
{
long long tmp=;
int sizz=tot-siz[nde];
for(int i=P[nde];i;i=Noww[i])
if(Goal[i]!=fth)
{
int G=Goal[i],S=siz[G];
tmp+=1ll*sizz*S,sizz+=S;
Getans(Goal[i],nde);
}
if(nde<=n) ans-=(tmp+tot-)*;
else ans+=*tmp*val[nde];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
scanf("%d%d",&t1,&t2),Link(t1,t2);
for(int i=;i<=n;val[i]=-,i++)
if(!dfn[i]) r=i,Tarjan_PBC(i);
for(int i=;i<=c;i++)
{
val[n+i]=ve[i].size();
for(int j=;j<val[n+i];j++)
Linka(n+i,ve[i][j]);
}
for(int i=;i<=n;i++)
if(!siz[i]) DFS(i,),tot=siz[i],Getans(i,);
printf("%lld",ans);
return ;
}