圆方树是一种在仙人掌图上常用的数据结构，但是这并不意味着圆方树只在仙人掌图上有用。事实上，在任何一张图上，我们都可以用相似的方法来构造一棵圆方树。
对于一张图，我们预处理出它的所有点双，然后对每一个点双建一个方点，其他处理方法和仙人掌上圆方树几乎相同。
这里的点双要如何预处理呢？我们考虑一个性质：当我们预处理出一张图的DFS树后，任何一条边属于且仅属于一个点双。
那么，我们就可以尝试找到一个点双中深度最浅的节点，然后由它构造出这个方点。
我们发现，当我们搜索完一个节点的子树后，如果子节点中的某一个节点的lw是这个节点，那么这个节点就是它所在的点双中深度最浅的节点。
这是因为，如果一个节点的lw节点是它的父节点，那么它和它的子树就没有任何返祖边能够到达比当前节点更浅的节点，也就说明如果当前节点在点双内，那么它一定是点双内最浅的节点。
有没有可能当前节点不在点双内呢？这是不可能的。如果有返祖边连向当前节点，那么当前节点显然不会成为割点；如果没有，那么当前节点所属的点双就一定只有两个点。
现在把目光投到这道题。
首先考虑点双的基本性质。我们发现，对于至少有三个点的点双，任取三个点，它们总是一对满足题意的三元组。
这是由于点双的定义，点双里没有割点，自然总是可以找到两点间的两条不相交的简单路径。
拓展这个结论，我们发现，如果一条简单路径经过一个点双，那么显然无论固定哪个点，这条路径都始终是一条简单路径。
故而，对于选定的起点和终点，我们可以分两类讨论。
倘若它们位于同一个点双，那么显然它们之间的满足题意的三元组个数恰好是这个点双的点数-2
对于不属于同一个点双的情况，它们之间有可能经过其他的点双，也有可能不经过。每经过一个点双，它们之间的满足题意的三元组个数就会加上这个点双的点的个数。
同时，答案还要加上起点和终点各自处在的点双的点数个数各自-1。
这要怎么统计呢？我们可以让每个方点的权值为点双中的点的数量，每个圆点的权值为-1，然后枚举点对统计路径和即可。
仔细一想觉得有点不对劲儿：这样的复杂度岂不是要n^2logn级别？妥妥地T啊。
正难则反，我们可以统计每个点对答案的贡献，也就是经过它的路径数乘上它本身的权值。而前者可以通过一个普通的树形DP求得。
这就做完了。
注意：
要注意每个点的子树外的节点的数量是相当于连通块大小减去它的子树大小，而非总节点数减去它的子树大小。故而要注意统计连通块大小。
#include<iostream>
#include<cstdio>
#define Fv(H,A,X) for(int A=H[X];A;A=e[A].nxt)
inline int Min(int A,int B){
return A<B?A:B;
}
struct ee{
int v;
int nxt;
}e[1200005];
int h0[100005],h[200005],et=0;
inline void Eadd(int *H,int U,int V){
e[++et]=(ee){V,H[U]};
H[U]=et;
}
inline void add(int *H,int U,int V){
Eadd(H,U,V);
Eadd(H,V,U);
}
int n,m;
int dfn[100005],lw[100005],cnt=0,nm=0;
int st[100005],tp=0;
int val[200005],nwsz;
long long ans=0;
inline void dfs(int X){
dfn[X]=lw[X]=++cnt;
st[++tp]=X;
++nwsz;
// 要注意每个点的子树外的节点的数量是相当于连通块大小减去它的子树大小，而非总节点数减去它的子树大小。故而要注意统计连通块大小。
Fv(h0,i,X){
if(!dfn[e[i].v]){
dfs(e[i].v);
lw[X]=Min(lw[X],lw[e[i].v]);
if(lw[e[i].v]==dfn[X]){
// 注意这里应当判定的是lw(v)=dfn(u)
val[++nm]=1;
for(int j=0;j!=e[i].v;--tp){
++val[nm];
j=st[tp];
add(h,nm,j);
}
add(h,X,nm);
}
}else{
lw[X]=Min(lw[X],dfn[e[i].v]);
}
}
}
int vis[200005],sz[200005];
inline void dfs2(int X){
vis[X]=1;
sz[X]=(X<=n);
Fv(h,i,X){
if(!vis[e[i].v]){
dfs2(e[i].v);
ans+=2ll*val[X]*sz[X]*sz[e[i].v];
sz[X]+=sz[e[i].v];
}
}
ans+=2ll*val[X]*sz[X]*(nwsz-sz[X]);
}
void init(){
scanf("%d%d",&n,&m);
nm=n;
for(int i=1;i<=n;++i){
val[i]=-1;
}
int u,v;
for(int i=1;i<=m;++i){
scanf("%d%d",&u,&v);
add(h0,u,v);
}
for(int i=1;i<=n;++i){
if(!dfn[i]){
nwsz=0;
dfs(i);
dfs2(i);
--tp;
}
}
printf("%lld\n",ans);
}
int main(){
init();
return 0;
}