#include<bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) (int)(x).size()
typedef long long ll;
typedef long double ld;
using namespace std;
#define int long long
const int N = (int)1e5 + 10;
const int M = (int)2e5 + 10;
vector < pair < int , int > > edges;
vector < int > g[N], tree[N];
int fup[N], tin[N], T, used[N];
bool bridge[M];
int get(int ide, int v){
return (edges[ide].fi == v ? edges[ide].se : edges[ide].fi);
}
void dfs(int v, int p){
fup[v] = tin[v] = T++;
used[v] = 1;
for(auto &e : g[v]){
int to = get(e , v);
if(!used[to]){
dfs(to, e);
}
if(e != p){
fup[v] = min(fup[v] , fup[to]);
}
}
if(p != -1){
if(fup[v] == tin[v]){
bridge[p] = 1;
}
}
}
int sz[N];
void colorit(int v, int clr){
used[v] = clr;
sz[clr]++;
for(auto &e : g[v]){
int to = get(e , v);
if(bridge[e]){
if(used[to] && used[to] != clr){
tree[used[to]].pb(clr);
tree[clr].pb(used[to]);
}
continue;
}
if(!used[to]){
colorit(to , clr);
}
}
}
int h[N];
ll ans3, ans2, ans1;
int dead[N], s[N];
void sizes(int v, int p){
s[v] = 1;
for(auto &u : tree[v]){
if(!dead[u] && u != p){
sizes(u , v);
s[v] += s[u];
}
}
}
int find_cen(int v , int p, int n){
for(auto &u : tree[v]){
if(u != p && !dead[u] && s[u] > n / 2)
return find_cen(u, v , n);
}
return v;
}
void dfs1(int v, int p, int H, vector < int > &layer){
h[v] = H;
layer.pb(v);
for(auto &u : tree[v]){
if(u == p || dead[u])
continue;
dfs1(u , v , H + sz[v], layer);
}
}
vector < int > now;
int cdused[N];
void decompose(int v){
now.pb(v);
dead[v] = 1;
cdused[v] = 1;
vector < vector < int > > sons;
for(auto &u : tree[v]){
if(!dead[u]){
vector < int > curlayer;
dfs1(u , -1, sz[v], curlayer);
sons.pb(curlayer);
}
}
ll sumSmH = 0, sumS = 0;
for(int f = 0; f < sz(sons); ++f){
for(auto &i : sons[f]){
sumS += sz[i];
sumSmH += 1ll * sz[i] * h[i];
}
}
for(int f = 0; f < sz(sons); ++f){
/// delete
ll curS = 0, curSmH =0;
for(auto &i : sons[f]){
curS += sz[i];
curSmH += 1ll * sz[i] * h[i];
}
for(auto &i : sons[f]){
ans3 += 1ll * sz[i] * (h[i] - sz[v]) * (sumS - curS);
ans3 += 1ll * sz[i] * (sumSmH - curSmH);
ans3 += 1ll * sz[i] * sz[v] * (h[i] - sz[v]) * 2;
}
}
for(auto &u : tree[v]){
if(!dead[u]){
sizes(u , -1);
decompose(find_cen(u , -1 , s[u]));
}
}
}
int solve(int n){
fill(used , used + N , 0);
for(int i = 0; i < n; ++i){
if(!used[i])
dfs(i , -1);
}
/// find t
int t = 0;
fill(used , used + N , 0);
for(int i = 0 ; i < n; ++i){
if(!used[i]){
t++;
colorit(i , t);
}
}
// /// COMPS
// for(int i = 0 ; i < n; ++i)
// cout << used[i] << ' ';
// cout << endl;
// cout << " EDGES TREE\n";
// for(int i = 1;i <= t; ++i){
// for(auto &u : tree[i])
// cout << i << ' ' << u << endl;
//// cout << endl;
// }
//
// cout << endl;
for(int j = 1; j <= t; ++j){
if(cdused[j])
continue;
now.clear();
sizes(j , -1);
decompose(find_cen(j , -1 , s[j]));
/// calc ans2 and ans1
ll ONE = 0, SEC = 0;
for(int i : now){
ONE += sz[i];
SEC += (sz[i] * (sz[i] - 1));
}
for(int i : now){
ans2 += 1ll * ((sz[i]-1)*(sz[i]-2) + (sz[i]-1)) * (ONE - sz[i]) * 2;
ans1 += 1ll * (1ll * sz[i] * (sz[i] - 1) * (sz[i] - 2));
}
}
cout << ans1 << ' ' << ans2 << ' ' << ans3 << endl;
// cout << ans1 + ans2 + ans3 << endl;
return ans1 + ans2 + ans3;
}
int used1[N];
int visited[N];
bool rek(int u, int v , int x, bool have){
if(u == x && !have){
return false;
}
if(u == x){
return true;
}
if(u == v)
have = 1;
for(int e : g[u]){
int to = get(e , u);
if(!visited[to]){
visited[to] = 1;
bool ans = rek(to , v , x , have);
if(ans)
return true;
visited[to] = 0;
}
}
return false;
}
int brute(int n){
int answer = 0;
for(int i = 0 ; i < n; ++i){
for(int m = 0; m < n; ++m){
for(int en = 0; en < n; ++en){
if(i == m || i == en || m == en)
continue;
fill(visited , visited + n , 0);
visited[i] = 1;
answer += rek(i , m , en, 0);
visited[i] = 0;
}
}
}
return answer;
}
mt19937 rng(1999999999973);
signed main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n , m;
bool debug = 0;
if(!debug){
cin >> n >> m;
for(int i = 0 ; i < m; ++i){
int u , v;
cin >> u >> v;
--u , --v;
edges.pb({u , v});
g[u].pb(i);
g[v].pb(i);
}
cout << brute(n) << '\n';
}else{
while(true){
int n = 10, m = 15;
vector < int > num(n * n);
edges.clear();
for(int i = 0 ; i < n; ++i)
g[i].clear();
iota(all(num) , 0);
shuffle(all(num) , rng);
int id = 0;
for(int i = 0; i < n * n; ++i){
if(m == 0)
break;
int u = num[i] / n, v = num[i] % n;
if(u == v)
continue;
m--;
edges.pb({u,v});
g[u].pb(id);
g[v].pb(id);
id++;
}
if(brute(n) == solve(n)){
cout << "OK\n";
}else{
cout << "WRONG\n";
for(auto &u : edges)
cout << u.fi << ' ' << u.se << endl;
cout << brute(n) << ' ' << solve(n) << endl;
return 0;
}
}
}
return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7
1 1 1
100000000 1 1 1
1
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
4 3
1 2
2 3
3 4
4 4
1 2
2 3
3 4
4 2
6 4
1 2
2 3
4 5
5 6
9 11
1 2
2 3
1 3
4 5
5 6
6 4
7 8
8 9
9 7
1 4
4 7
10 12
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7
10 1
10 4
10 7
*/
