// https://oj.uz/problem/view/APIO18_duathlon
#include<iostream>
#include<vector>
#include<cassert>
std::vector<std::vector<int>> adjl;
int nnode;
int lastnum=0;
std::vector<int> dnum,dlow;
std::vector<int> stk;
// adjlist for circle-square-tree
// node with index < nnode are real
std::vector<std::vector<int>> cst_adjl;
int64_t ans;
void dfs(int node,int par){
assert(dnum[node]==0);
dnum[node]=dlow[node]=++lastnum;
stk.push_back(node);
for(int ad:adjl[node]){
if(ad==par)continue;
if(dnum[ad])
dlow[node]=std::min(dlow[node],dnum[ad]);
else{ // ad is a child of node
dfs(ad,node);
if(dlow[ad]>=dnum[node]){
// it creates a new biconnected component
auto iter=--stk.end();
while(*iter!=ad)--iter;
std::vector<int> v;
v.reserve(stk.end()-iter+1);
v.assign(iter,stk.end());
v.push_back(node);
int newnode=(int)cst_adjl.size();
assert(newnode>=nnode);
for(int x:v)
cst_adjl[x].push_back(newnode);
cst_adjl.push_back(std::move(v));
stk.erase(iter,stk.end());
}else{
dlow[node]=std::min(dlow[node],dlow[ad]);
}
}
}
}
std::vector<int> cst_par,
cst_stsize /* only includes real nodes */;
void dfs2(int node){
int& cst_stsize_node=cst_stsize[node];
assert(cst_stsize_node==0);
cst_stsize_node=node<nnode;
for(int adj:cst_adjl[node])if(adj!=cst_par[node]){
cst_par[adj]=node;
dfs2(adj);
cst_stsize_node+=cst_stsize[adj];
}
assert(cst_stsize_node>0);
}
std::vector<int64_t> ssqr;
int64_t sqr(int x){return (int64_t)x*x;}
int ccsize; // size of currently considering connected component, in real nodes
void dfs3(int node){
if(node<nnode){
// consider c == node. how many of (s,t) pairs are over-counted?
for(int d:cst_adjl[node]){
// assume s and t are "to the direction of d" from c
assert(d>=nnode&&cst_adjl[d].size()>1);
int64_t& ssqr_d=ssqr[d-nnode];
if(ssqr_d==0){
// compute ssqr_d first
assert(d!=cst_par[node]);
for(int x:cst_adjl[d])
if(cst_par[d]==x)
ssqr_d+=sqr(ccsize-cst_stsize[d]);
else
ssqr_d+=sqr(cst_stsize[x]);
assert(ssqr_d!=0);
ans-=ssqr_d;
ans+=sqr(ccsize-cst_stsize[d]);
}else{
assert(d==cst_par[node]);
ans-=ssqr_d;
ans+=sqr(cst_stsize[node]);
}
}
}
for(int adj:cst_adjl[node])if(adj!=cst_par[node]){
dfs3(adj);
}
}
int main(){
std::ios::sync_with_stdio(0);std::cin.tie(0);
int nedge;std::cin>>nnode>>nedge;
adjl.resize(nnode);
for(int i=nedge;i-->0;){
int u,v;std::cin>>u>>v;
--u;--v;
adjl[u].push_back(v);
adjl[v].push_back(u);
}
dnum.resize(nnode);
dlow.resize(nnode);
ans=0;
cst_adjl.resize(nnode);
std::vector<int> fnodes; // each connected component has exactly one fnode
for(int node=0;node<nnode;++node)if(dnum[node]==0){
fnodes.push_back(node);
assert(stk.empty());
dfs(node,-1);
assert(stk.size()==1&&stk[0]==node);
stk.clear();
}
cst_par.assign(cst_adjl.size(),-1);
cst_stsize.resize(cst_adjl.size());
ssqr.resize(cst_adjl.size()-nnode);
for(int x:fnodes){
assert(x<nnode);
dfs2(x);
ccsize=cst_stsize[x];
ans+=ccsize // for each way to choose vertex c
*(ccsize-1LL)*(ccsize-1); // there are at most % ways to choose s and t
// (allow them to overlap but not the same as c)
dfs3(x);
}
std::cout<<ans<<'\n';
}
/*
4 3
1 2
2 3
3 4
4 4
1 2
2 3
3 4
4 2
5 6
1 2 1 3 2 3 2 4 2 5 4 5
*/
