#include <iostream>
#include <vector>
using namespace std;
#define int long long
const int N = 1e5 + 10,lg = 18;
int par[N][lg + 1];
int Par[N];
void dfs(int u,int p = 0){
hei[u] = hei[p] + 1;
par[u][0] = p;
for (int i=1;i<=lg;i++)
par[u][i] = par[par[u][i-1]][i-1];
for (int i : nei[u])
if (i != u)
dfs(i,u);
}
int root(int v){
if (Par[v] == 0)
return v;
Par[v] = root(Par[v]);
return Par[v];
}
void lift(int & v,int d){
for (int i=0;i<=lg;i++)
if ((1<<i) & d)
v = par[v][i];
}
int lca(int u,int v){
if (hei[u] > hei[v])
swap(u,v);
lift(v,hei[v] - hei[u]);
if (u == v)
return u;
for (int i=lg;i>=0;i--)
if (par[u][i] != par[v][i])
u = par[u][i], v = par[v][i];
return par[u][0];
}
void dfs31(int u,int p = -1){
Seen[u] = true;
ch[u] = 1;
for (int i : nei[u])
if (i != p)
dfs31(i,u),ch[u] += ch[i];
}
int ans = 0;
void dfs32(int u,int rt,int p = -1){
int S = ch[rt] - ch[u];
for (int i : nei[u])
if (i != p)
ans += ch[i] * S,S += ch[i];
for (int i : nei[u])
if (i != p)
dfs32(i,rt,u);
}
void sub45(int n){
for (int i=1;i<=n;i++)
if (!Seen[i]){
dfs31(i);
dfs32(i,i);
}
}
signed main(){
int n,m;
cin>>n>>m;
vector<pair<int,int>> vec;
for (int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
int u = root(a);
int v = root(b);
if (u == v){
vec.push_back({a,b});
continue;
}
Par[u] = Par[v];
nei[a].push_back(b);
nei[b].push_back(a);
}
for (int i=1;i<=n;i++)
if (hei[i] == 0)
dfs(i);
sub45();
ans = ans * 2;
for (auto [a,b] : vec){
int l = lca(a,b);
int d = hei[a] + hei[b] - 2 * h[l];
for (int i=1;i<=l;i++)
ans -= (i-1) * (l - i) * 2;
ans += l * (l - 1) * (l - 2);
}
cout<<ans<<'\n';
}
/*
16 15
1 2
1 3
3 4
3 5
3 6
5 7
5 8
5 9
2 10
2 11
11 12
11 13
13 15
13 16
13 14
*/
Compilation message
count_triplets.cpp: In function 'void dfs(long long int, long long int)':
count_triplets.cpp:11:2: error: 'hei' was not declared in this scope
11 | hei[u] = hei[p] + 1;
| ^~~
count_triplets.cpp:17:15: error: 'nei' was not declared in this scope
17 | for (int i : nei[u])
| ^~~
count_triplets.cpp: In function 'long long int lca(long long int, long long int)':
count_triplets.cpp:36:6: error: 'hei' was not declared in this scope
36 | if (hei[u] > hei[v])
| ^~~
count_triplets.cpp:38:9: error: 'hei' was not declared in this scope
38 | lift(v,hei[v] - hei[u]);
| ^~~
count_triplets.cpp: In function 'void dfs31(long long int, long long int)':
count_triplets.cpp:59:2: error: 'Seen' was not declared in this scope
59 | Seen[u] = true;
| ^~~~
count_triplets.cpp:60:2: error: 'ch' was not declared in this scope
60 | ch[u] = 1;
| ^~
count_triplets.cpp:61:15: error: 'nei' was not declared in this scope
61 | for (int i : nei[u])
| ^~~
count_triplets.cpp: In function 'void dfs32(long long int, long long int, long long int)':
count_triplets.cpp:67:10: error: 'ch' was not declared in this scope
67 | int S = ch[rt] - ch[u];
| ^~
count_triplets.cpp:68:15: error: 'nei' was not declared in this scope
68 | for (int i : nei[u])
| ^~~
count_triplets.cpp:71:15: error: 'nei' was not declared in this scope
71 | for (int i : nei[u])
| ^~~
count_triplets.cpp: In function 'void sub45(long long int)':
count_triplets.cpp:78:8: error: 'Seen' was not declared in this scope
78 | if (!Seen[i]){
| ^~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:104:3: error: 'nei' was not declared in this scope
104 | nei[a].push_back(b);
| ^~~
count_triplets.cpp:109:7: error: 'hei' was not declared in this scope
109 | if (hei[i] == 0)
| ^~~
count_triplets.cpp:112:8: error: too few arguments to function 'void sub45(long long int)'
112 | sub45();
| ^
count_triplets.cpp:76:6: note: declared here
76 | void sub45(int n){
| ^~~~~
count_triplets.cpp:118:11: error: 'hei' was not declared in this scope
118 | int d = hei[a] + hei[b] - 2 * h[l];
| ^~~
count_triplets.cpp:118:33: error: 'h' was not declared in this scope
118 | int d = hei[a] + hei[b] - 2 * h[l];
| ^
count_triplets.cpp:118:7: warning: unused variable 'd' [-Wunused-variable]
118 | int d = hei[a] + hei[b] - 2 * h[l];
| ^
