首先我们可以在枚举 $u$ 的出边时给其出点打上 $u$ 的时间戳，这样在枚举 $v$ 的出边时即可 $O(1)$ 去判断 $w$ 是不是 $u$ 的出点。

那么考虑对于每一条边 $<u \rightarrow v>$，它对复杂度造成的贡献是 $out_v$，因此总复杂度即为 $\sum_{i = 1}^m out_{v_i}$，其中 $v_i$ 是第 $i$ 条边指向的点，$out_v$ 是点 $v$ 的出度。

考虑分情况讨论。

1. 当 $v$ 在原图（无向图）上的度数不大于 $\sqrt m$ 时，由于新图每个节点的出度不可能大于原图的度数，所以 $out_v = O(\sqrt m)$。
2. 当 $v$ 在原图上的度数大于 $\sqrt m$ 时，注意到它只能向原图中度数不小于它的点连边，又因为原图中所有的点的度数和为 $O(m)$，所以原图中度数大于 $\sqrt m$ 的点只有 $O(\sqrt m)$ 个。因此 $v$ 的出边只有 $O(\sqrt m)$ 条，也即 $out_v = O(\sqrt m)$。

因此所有节点的出度均为 $O(\sqrt m)$，总复杂度 $\sum_{i = 1}^m out_{v_i} = O(m \sqrt m)$。

Code

#include <cstdio>
#include <vector>

const int maxn = 200005;

int n, m, ans;
int dgr[maxn], A[maxn], B[maxn], vistime[maxn];
std::vector<int> e[maxn];

int main() {
  qr(n); qr(m);
  for (int i = 1; i <= m; ++i) {
    qr(A[i]); qr(B[i]);
    ++dgr[A[i]]; ++dgr[B[i]];
  }
  for (int u, v; m; --m) {
    u = A[m]; v = B[m];
    if (dgr[u] > dgr[v]) {
      std::swap(u, v);
    } else if ((dgr[u] == dgr[v]) && (u > v)) {
      std::swap(u, v);
    }
    e[u].push_back(v);
  }
  for (int u = 1; u <= n; ++u) {
    for (auto v : e[u]) vistime[v] = u;
    for (auto v : e[u]) {
      for (auto w : e[v]) if (vistime[w] == u) {
        ++ans;
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}