#include <iostream> #include <queue> #include <set> using namespace std; const int N = 1<<17; int Par[N], Sz[N]; long long Ans; set<int> dir[N], rev[N], imd[N]; queue<pair<int, int>> Q; int root(int v){ return (Par[v] == v ? v : Par[v] = root(Par[v])); } void AddEdge(int A, int B){ dir[A].insert(B); rev[B].insert(A); if (dir[B].find(A) != dir[B].end()) Q.push({A, B}); } void connect(int A, int B){ if (A == B) return; if (imd[A].size() + dir[A].size() + rev[A].size() < imd[B].size() + dir[B].size() + rev[B].size()) swap(A, B); Ans += 1LL * Sz[B] * imd[A].size() + 1LL * Sz[A] * imd[B].size(); Par[B] = A; Sz[A] += Sz[B]; for (int i : imd[B]){ if (imd[A].find(i) == imd[A].end()) imd[A].insert(i); else Ans -= Sz[A]; } dir[A].erase(B), dir[B].erase(A); rev[A].erase(B), rev[B].erase(A); for (int i : dir[B]){ rev[i].erase(B); AddEdge(A, i); } for (int i : rev[B]){ dir[i].erase(B); AddEdge(i, A); } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); for (int i = 1;i<N;i++) Par[i] = i, Sz[i] = 1, imd[i].insert(i); int n, m, a, b, A, B; cin>>n>>m; while (m--){ cin>>a>>b; A = root(a), B = root(b); if (A != B and imd[B].find(a) == imd[B].end()){ imd[B].insert(a); Ans += Sz[B]; AddEdge(A, B); while (Q.size() > 0){ auto [c, d] = Q.front(); Q.pop(); connect(root(c), root(d)); } } cout<<Ans<<'\n'; } }