問題はこちら。

橋１から壊していくのではなく、橋 M から繋いでいくと考える。

橋 i が A, B とつなぐとき、A, B の属する連結成分の大きさがそれぞれ s, t だったとすると問題文中で定義されている「不便さ」は s * t 減ることが計算するとわかる。

class UnionFind():
    # union と same と size をメソッドにもつ UnionFind木

N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]

ans = [0]*(M + 1)
ans[M] = N*(N - 1) // 2
X = UnionFind(N)
for i in reversed(range(M)):
   A, B = edges[i]
   A -= 1; B -= 1
   s, t = X.size(A), X.size(B)
   if X.same(A, B):
       ans[i] = ans[i + 1]
       continue
   ans[i] = ans[i + 1] - s * t
   X.union(A, B)
   
print('\n'.join(map(str, ans[1:])))
​