#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'
template <typename A, typename B>
bool chmin(A &a, const B &b) {
if(a > b) {
return a = b, true;
}
return false;
}
template <typename A, typename B>
bool chmax(A &a, const B &b) {
if(a < b) {
return a = b, true;
}
return false;
}
void solve() {
int n, m; cin >> n >> m;
vector<vector<int>> adj(n);
vector<pair<int, int>> edges;
vector<int> d(n);
for(int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
adj[--u].pb(--v);
adj[v].pb(u);
d[u]++, d[v]++;
edges.pb({u, v});
}
if(n <= 50) {
int ans = 0;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
queue<int> q;
q.emplace(i);
vector<int> used(n), d(n), is(n);
for(auto to : adj[j]) {
is[to] = 1;
}
used[i] = 1;
while(!q.empty()) {
int v = q.front();
q.pop();
bool flag = false;
for(auto to : adj[v]) {
if(!used[to] && to != j) {
if(flag || is[v]) d[to] = 1;
else d[to] = d[v] + 1;
used[to] = 1;
q.emplace(to);
flag = true;
}
}
}
// cout << i + 1 << ' ' << j + 1 << ": ";
for(auto to : adj[j]) {
ans += 2 * d[to];
// cout << d[to] << ' ';
}
cout << nl;
}
}
cout << ans << nl;
return;
}
int s3 = 1;
for(int i = 0; i < n; i++) {
if(d[i] > 2) {
s3 = false;
break;
}
}
if(s3) {
vector<int> used(n);
int cnt = 0, is = 0;
auto dfs = [&](auto &&self, int v, int p) -> void {
used[v] = true;
cnt++;
for(auto to : adj[v]) {
if(to == p) continue;
if(used[to]) {
is = 1;
continue;
}
self(self, to, v);
}
};
int ans = 0;
for(int i = 0; i < n; i++) {
if(!used[i]) {
cnt = 0;
is = 0;
dfs(dfs, i, -1);
if(is) {
ans += cnt * (cnt - 2) * (cnt - 1);
} else {
for(int j = 0; j < cnt; j++) {
ans += 2 * j * (cnt - 1 - j);
}
}
}
}
cout << ans << nl;
return;
}
auto solve1 = [&]() {
int ans = 0;
for(int u = 0; u < n; u++) {
queue<int> q;
vector<int> d(n, -1), sum(n);
q.emplace(u);
d[u] = 0;
while(!q.empty()) {
int v = q.front();
q.pop();
ans += sum[v];
for(auto to : adj[v]) {
if(d[to] == -1) {
d[to] = d[v] + 1;
sum[to] += d[v];
q.emplace(to);
}
}
}
}
return ans;
};
vector<int> s(n, 1), used(n), par(n);
int ans = 0;
auto dfs = [&](auto &&self, int v, int p, vector<int> &output) -> void {
used[v] = true;
par[v] = p;
for(auto to : adj[v]) {
if(to == p) continue;
self(self, to, v, output);
s[v] += s[to];
}
output.pb(v);
};
vector<int> output;
auto solve2 = [&]() {
for(int i = 0; i < n; i++) {
if(!used[i]) {
output.clear();
dfs(dfs, i, -1, output);
for(auto v : output) {
for(auto to : adj[v]) {
if(to == par[v]) {
ans += (s[v] - 1) * (s[i] - s[v]);
} else ans += s[to] * (s[i] - 1 - s[to]);
}
}
}
}
};
auto print = [&](int x) {
cout << x << nl;
};
solve2();
cout << ans << nl;
}
/**
4 3
1 2
2 3
3 4
4 4
1 2
2 3
3 4
4 2
**/
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |