#include <iostream> #include <vector> #include <set> #include <map> #include <algorithm> using namespace std; using ll = long long; int const N = 2e5 + 5; vector<int> graph[N]; vector<int> tree[N]; int n, m, ts, dfn[N], low[N], stk[N], tp, ccnt, p[N], w[N]; ll ans; struct VBCC { struct EdgeNode { int u, v; int lc, rc, pa; bool series; EdgeNode(int u_, int v_, bool series_ = false, int lc_ = -1, int rc_ = -1): u(u_), v(v_), series(series_), lc(lc_), rc(rc_), pa(-1) {} }; vector<EdgeNode> e; map<int, map<int, int>> mp; int key; int add_edge(int x, int y) { int id = e.size(); e.emplace_back(x, y); auto& mpx = mp[x]; if (auto it = mpx.find(y); it == mpx.end()) { mpx[y] = id; mp[y][x] = id; } else { int nxt = e.size(); e.emplace_back(x, y, false, it->second, id); e[it->second].pa = e[id].pa = nxt; it->second = nxt; mp[y][x] = nxt; } return id; } void compress() { vector<decltype(mp)::iterator> todo; for (auto it = mp.begin(); it != mp.end(); ++it) { if (it->second.size() == 2) todo.push_back(it); } while (not todo.empty()) { auto it = todo.back(); todo.pop_back(); if (it->second.size() != 2) continue; int x = it->first; auto ity = it->second.begin(); auto itz = next(ity); int y = ity->first; int z = itz->first; int id = add_edge(y, z); e[id].lc = ity->second; e[id].rc = itz->second; e[id].series = true; e[ity->second].pa = e[itz->second].pa = id; it->second.clear(); mp[y].erase(x); mp[z].erase(x); if (auto it = mp.find(y); it->second.size() == 2) todo.push_back(it); if (auto it = mp.find(z); it->second.size() == 2) todo.push_back(it); } } struct eval_res { int cut_cnt, dw, u, v; bool key_cut; void print() { // cerr << "u: " << u << " v: " << v << endl; } }; eval_res series_compose(eval_res x, eval_res y) { // cerr << "series: " << endl; x.print(); y.print(); int l, mid, r; if (x.u == y.u) { l = x.v, mid = x.u, r = y.v; } if (x.u == y.v) { l = x.v, mid = x.u, r = y.u; } if (x.v == y.u) { l = x.u, mid = x.v, r = y.v; } if (x.v == y.v) { l = x.u, mid = x.v, r = y.u; } eval_res ret = {x.cut_cnt + y.cut_cnt + w[mid], x.dw + y.dw, l, r, x.key_cut or y.key_cut or mid == key}; ans += ll(w[l] + x.cut_cnt) * ll(w[r] + y.cut_cnt); if (l == key or x.key_cut) ret.dw += w[r] + y.cut_cnt; if (r == key or y.key_cut) ret.dw += w[l] + x.cut_cnt; return ret; } eval_res parallel_compose(eval_res x, eval_res y, bool last) { // cerr << "parallel: " << endl; x.print(); y.print(); eval_res ret = {0, x.dw + y.dw, x.u, x.v, false}; ans -= ll(w[x.u]) * w[x.v]; if (x.u == key) ret.dw -= w[x.v]; if (x.v == key) ret.dw -= w[x.u]; if (last) { ans += ll(x.cut_cnt) * y.cut_cnt; if (x.key_cut) ret.dw += y.cut_cnt; if (y.key_cut) ret.dw += x.cut_cnt; } return ret; } eval_res eval(int x) { // cerr << "eval: " << e[x].u << ' ' << e[x].v << endl; if(e[x].lc != -1) { // cerr << "lc: " << e[e[x].lc].u << e[e[x].lc].v << " rc: " << e[e[x].rc].u << e[e[x].rc].v << endl; if (e[x].series) { return series_compose(eval(e[x].lc), eval(e[x].rc)); } else { return parallel_compose(eval(e[x].lc), eval(e[x].rc), e[x].pa == -1); } } else { // cerr << "leaf" << endl; ans += ll(w[e[x].u]) * w[e[x].v]; if (e[x].u == key) { return {0, w[e[x].v], e[x].u, e[x].v, false}; } if (e[x].v == key) { return {0, w[e[x].u], e[x].u, e[x].v, false}; } return {0, 0, e[x].u, e[x].v, false}; } } void calc(int key_) { compress(); auto it = find_if(e.begin(), e.end(), [&](const EdgeNode& edg) { return edg.pa == -1; }); if (find_if(next(it), e.end(), [&](const EdgeNode& edg) { return edg.pa == -1; }) != e.end()) return; key = key_; w[key] += eval(it - e.begin()).dw; // cerr << "w " << key << " = " << w[key] << endl; // cerr << "ans = " << ans << endl; } } g[N]; void tarjan(int x) { low[x] = dfn[x] = ++ts; stk[++tp] = x; for (int y: graph[x]) { if (!dfn[y]) { tarjan(y); low[x] = min(low[x], low[y]); if (low[y] == dfn[x]) { ccnt++; for (int t = 0; t != y; tp--) { t = stk[tp]; tree[ccnt].push_back(t); tree[t].push_back(ccnt); p[t] = ccnt; } tree[ccnt].push_back(x); tree[x].push_back(ccnt); p[ccnt] = x; } } else { low[x] = min(low[x], dfn[y]); } } } void dfs(int x) { // cerr << "dfs: " << x << endl; for (auto t: tree[x]) { if (t != p[x]) { dfs(t); } } if (x > n) g[x].calc(p[x]); } #include <random> int rnd[N]; mt19937 rg(time(0)); int main() { ios::sync_with_stdio(false); cin >> n >> m; // for (int i = 1; i <= n; i++) rnd[i] = i; // shuffle(rnd + 1, rnd + n + 1, rg); // for (int i = 1; i <= n; i++) cerr << rnd[i] << ' '; // cerr << endl; for (int i = 0, x, y; i < m; i++) { cin >> x >> y; // x = rnd[x]; // y = rnd[y]; graph[x].push_back(y); graph[y].push_back(x); } vector<int> root; ccnt = n; for (int x = 1; x <= n; x++) { if (!dfn[x]) { tarjan(x); tp--; root.push_back(x); } } for (int x = 1; x <= n; x++) { for (auto y: graph[x]) { if ((p[p[x]] == y) || (p[x] == p[y] && x < y)) { g[p[x]].add_edge(x, y); } } } fill(w, w + n + 1, 1); for (auto x: root) { dfs(x); } cout << ans << endl; }