1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

struct Edge { int to; int id; };

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  if (!(cin >> n >> m)) return 0;

  vector<vector<Edge>> graph(n + 1);
  vector<int> U(m + 1), V(m + 1);
  for (int i = 1; i <= m; ++i) {
    int a, b; cin >> a >> b;
    U[i] = a; V[i] = b;
    graph[a].push_back({b, i});
    graph[b].push_back({a, i});
  }

  // Tarjan BCC -> Block-Cut Tree
  vector<int> disc(n + 1, 0), low(n + 1, 0);
  int timer = 0;
  vector<int> edgeStack; edgeStack.reserve(m);
  vector<vector<int>> bcAdj(n + m + 5);
  vector<int> bSize(n + m + 5, 0);
  vector<int> mark(n + 1, 0);
  int markTick = 1;
  int bccCnt = 0;

  function<void(int,int)> dfs = [&](int u, int peid) {
    disc[u] = low[u] = ++timer;
    for (const auto &e : graph[u]) {
      int v = e.to, eid = e.id;
      if (eid == peid) continue;
      if (!disc[v]) {
        edgeStack.push_back(eid);
        dfs(v, eid);
        low[u] = min(low[u], low[v]);
        if (low[v] >= disc[u]) {
          ++bccCnt; int bNode = n + bccCnt;
          vector<int> compVerts;
          while (true) {
            int ce = edgeStack.back(); edgeStack.pop_back();
            int a = U[ce], b = V[ce];
            if (mark[a] != markTick) { mark[a] = markTick; compVerts.push_back(a); }
            if (mark[b] != markTick) { mark[b] = markTick; compVerts.push_back(b); }
            if (ce == eid) break;
          }
          ++markTick;
          bSize[bNode] = (int)compVerts.size();
          for (int x : compVerts) {
            bcAdj[x].push_back(bNode);
            bcAdj[bNode].push_back(x);
          }
        }
      } else if (disc[v] < disc[u]) {
        edgeStack.push_back(eid);
        low[u] = min(low[u], disc[v]);
      }
    }
  };

  for (int i = 1; i <= n; ++i) if (!disc[i]) dfs(i, 0);

  int totalNodes = n + bccCnt;

  // Tree DP on Block-Cut Forest
  vector<int> parent(totalNodes + 1, -1);
  vector<int> compId(totalNodes + 1, -1);
  vector<int64> subOrig(totalNodes + 1, 0);
  vector<int64> compOrigSum; compOrigSum.reserve(totalNodes + 1);
  int compCnt = 0;

  function<void(int,int,int)> dfsTree = [&](int u, int p, int cid) {
    parent[u] = p; compId[u] = cid;
    subOrig[u] = (u <= n ? 1LL : 0LL);
    for (int v : bcAdj[u]) if (v != p) { dfsTree(v, u, cid); subOrig[u] += subOrig[v]; }
  };

  vector<char> visited(totalNodes + 1, 0);
  for (int u = 1; u <= totalNodes; ++u) if (!visited[u]) {
    vector<int> nodes; queue<int> q; q.push(u); visited[u] = 1;
    while (!q.empty()) { int x = q.front(); q.pop(); nodes.push_back(x);
      for (int v : bcAdj[x]) if (!visited[v]) { visited[v] = 1; q.push(v); } }
    dfsTree(u, -1, compCnt);
    compOrigSum.push_back(subOrig[u]);
    ++compCnt;
  }

  // total ordered triples per connected component
  int64 totalOrderedTriples = 0;
  for (int id = 0; id < compCnt; ++id) {
    int64 N = compOrigSum[id];
    if (N >= 3) totalOrderedTriples += N * (N - 1) * (N - 2);
  }

  auto sideSize = [&](int P, int B) -> int64 {
    if (parent[B] == P) return subOrig[B];
    if (parent[P] == B) return compOrigSum[compId[P]] - subOrig[P];
    return subOrig[B];
  };

  long long bad = 0;
  for (int P = 1; P <= n; ++P) {
    if (bcAdj[P].empty()) continue;
    int64 sum1 = 0, sum2 = 0; vector<int64> S; S.reserve(bcAdj[P].size());
    for (int B : bcAdj[P]) { int64 s = sideSize(P, B); S.push_back(s); sum1 += s; sum2 += s * s; }
    for (size_t i = 0; i < bcAdj[P].size(); ++i) {
      int B = bcAdj[P][i]; int64 w = (int64)bSize[B] - 1; if (w <= 0) continue;
      int64 sB = S[i]; int64 other1 = sum1 - sB; int64 other2 = sum2 - sB * sB;
      bad += w * (other2 + other1);
    }
  }

  cout << (totalOrderedTriples - bad) << '\n';
  return 0;
}