#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]));
}
}
}
signed main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n , m;
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);
}
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 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
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5708 KB |
Output is correct |
2 |
Correct |
3 ms |
5836 KB |
Output is correct |
3 |
Correct |
3 ms |
5836 KB |
Output is correct |
4 |
Correct |
3 ms |
5792 KB |
Output is correct |
5 |
Correct |
3 ms |
5796 KB |
Output is correct |
6 |
Correct |
3 ms |
5796 KB |
Output is correct |
7 |
Incorrect |
3 ms |
5836 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5708 KB |
Output is correct |
2 |
Correct |
3 ms |
5836 KB |
Output is correct |
3 |
Correct |
3 ms |
5836 KB |
Output is correct |
4 |
Correct |
3 ms |
5792 KB |
Output is correct |
5 |
Correct |
3 ms |
5796 KB |
Output is correct |
6 |
Correct |
3 ms |
5796 KB |
Output is correct |
7 |
Incorrect |
3 ms |
5836 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
19900 KB |
Output is correct |
2 |
Correct |
100 ms |
19812 KB |
Output is correct |
3 |
Correct |
146 ms |
21196 KB |
Output is correct |
4 |
Correct |
118 ms |
21852 KB |
Output is correct |
5 |
Correct |
125 ms |
19624 KB |
Output is correct |
6 |
Correct |
207 ms |
21676 KB |
Output is correct |
7 |
Correct |
154 ms |
19832 KB |
Output is correct |
8 |
Correct |
168 ms |
21132 KB |
Output is correct |
9 |
Correct |
153 ms |
18700 KB |
Output is correct |
10 |
Correct |
178 ms |
19096 KB |
Output is correct |
11 |
Correct |
68 ms |
17020 KB |
Output is correct |
12 |
Correct |
90 ms |
16904 KB |
Output is correct |
13 |
Correct |
63 ms |
17052 KB |
Output is correct |
14 |
Correct |
86 ms |
16816 KB |
Output is correct |
15 |
Correct |
63 ms |
16624 KB |
Output is correct |
16 |
Correct |
51 ms |
16312 KB |
Output is correct |
17 |
Correct |
8 ms |
10880 KB |
Output is correct |
18 |
Correct |
8 ms |
10956 KB |
Output is correct |
19 |
Correct |
7 ms |
10828 KB |
Output is correct |
20 |
Correct |
7 ms |
10828 KB |
Output is correct |
21 |
Correct |
8 ms |
10828 KB |
Output is correct |
22 |
Correct |
11 ms |
10700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5964 KB |
Output is correct |
2 |
Correct |
4 ms |
5964 KB |
Output is correct |
3 |
Correct |
4 ms |
5964 KB |
Output is correct |
4 |
Correct |
4 ms |
5964 KB |
Output is correct |
5 |
Correct |
6 ms |
5964 KB |
Output is correct |
6 |
Correct |
4 ms |
5964 KB |
Output is correct |
7 |
Correct |
4 ms |
5964 KB |
Output is correct |
8 |
Correct |
4 ms |
5964 KB |
Output is correct |
9 |
Correct |
4 ms |
5964 KB |
Output is correct |
10 |
Correct |
4 ms |
5964 KB |
Output is correct |
11 |
Correct |
4 ms |
5964 KB |
Output is correct |
12 |
Correct |
4 ms |
5964 KB |
Output is correct |
13 |
Correct |
4 ms |
5936 KB |
Output is correct |
14 |
Correct |
4 ms |
5964 KB |
Output is correct |
15 |
Correct |
4 ms |
5928 KB |
Output is correct |
16 |
Correct |
3 ms |
5836 KB |
Output is correct |
17 |
Correct |
3 ms |
6004 KB |
Output is correct |
18 |
Correct |
3 ms |
5964 KB |
Output is correct |
19 |
Correct |
4 ms |
6092 KB |
Output is correct |
20 |
Correct |
4 ms |
6016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
204 ms |
23396 KB |
Output is correct |
2 |
Correct |
172 ms |
23216 KB |
Output is correct |
3 |
Correct |
231 ms |
23536 KB |
Output is correct |
4 |
Correct |
176 ms |
23492 KB |
Output is correct |
5 |
Correct |
177 ms |
23140 KB |
Output is correct |
6 |
Correct |
319 ms |
26384 KB |
Output is correct |
7 |
Correct |
308 ms |
25912 KB |
Output is correct |
8 |
Correct |
311 ms |
25356 KB |
Output is correct |
9 |
Correct |
271 ms |
24752 KB |
Output is correct |
10 |
Correct |
176 ms |
22136 KB |
Output is correct |
11 |
Correct |
178 ms |
24492 KB |
Output is correct |
12 |
Correct |
160 ms |
22452 KB |
Output is correct |
13 |
Correct |
179 ms |
22444 KB |
Output is correct |
14 |
Correct |
111 ms |
20944 KB |
Output is correct |
15 |
Correct |
88 ms |
20144 KB |
Output is correct |
16 |
Correct |
60 ms |
17608 KB |
Output is correct |
17 |
Correct |
75 ms |
29324 KB |
Output is correct |
18 |
Correct |
77 ms |
29236 KB |
Output is correct |
19 |
Correct |
75 ms |
28328 KB |
Output is correct |
20 |
Correct |
75 ms |
27412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5964 KB |
Output is correct |
2 |
Correct |
4 ms |
5964 KB |
Output is correct |
3 |
Incorrect |
5 ms |
5964 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
186 ms |
23524 KB |
Output is correct |
2 |
Correct |
203 ms |
23104 KB |
Output is correct |
3 |
Incorrect |
161 ms |
20528 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5708 KB |
Output is correct |
2 |
Correct |
3 ms |
5836 KB |
Output is correct |
3 |
Correct |
3 ms |
5836 KB |
Output is correct |
4 |
Correct |
3 ms |
5792 KB |
Output is correct |
5 |
Correct |
3 ms |
5796 KB |
Output is correct |
6 |
Correct |
3 ms |
5796 KB |
Output is correct |
7 |
Incorrect |
3 ms |
5836 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5708 KB |
Output is correct |
2 |
Correct |
3 ms |
5836 KB |
Output is correct |
3 |
Correct |
3 ms |
5836 KB |
Output is correct |
4 |
Correct |
3 ms |
5792 KB |
Output is correct |
5 |
Correct |
3 ms |
5796 KB |
Output is correct |
6 |
Correct |
3 ms |
5796 KB |
Output is correct |
7 |
Incorrect |
3 ms |
5836 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |