Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A, B = [], []
g = {}
for i in range(1, N+1):
    g[i] = []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    g[a].append(b)
    g[b].append(a)


def dfs(graph, start):
    visited = []
    stack = []
    stack.append(start)
    result = []
    while len(stack) > 0:
        next = stack.pop()
        if next in visited:
            continue
        result.append(next)
        visited.append(next)
        for nei in graph[next]:
            stack.append(nei)
    return result


def wfs(graph, start):
    visited = []
    queue = []
    queue.append(start)
    result = []
    while len(queue) > 0:
        next_city = queue.pop(0)
        if next_city in visited:
            continue
        result.append(next_city)
        visited.append(next_city)
        for nei in graph[next_city]:
            queue.append(nei)
    return result


for i in range(M):
    ans = 0
    g[A[i]].remove(B[i])
    g[B[i]].remove(A[i])
    for j in range(1, N+1):
        # print(wfs(g, j))
        for k in range(j, N+1):
            if k not in wfs(g, j):
                ans += 1
    print(ans)


Fixed submission:
class UnionFind():
    # 初期化
    # 全てのノードの親は -1 とする
    def __init__(self, n):
        self.par = [-1] * n

    # xがどのグループに属しているか調べる
    def root(self, x):
        # xが親のとき
        if self.par[x] < 0:
            return x
        # xの親がさらに親をもつとき、それをxの親とする
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    # 自分のいるグループの頂点数を調べる
    def size(self, x):
        return -self.par[self.root(x)]

    # xとyをくっつける
    def connect(self, x, y):
        x = self.root(x)
        y = self.root(y)
        # すでにくっついていたらくっつけない
        if x == y:
            return

        # 大きい方(x)に小さい方(y)をくっつける
        if self.size(x) < self.size(y):
            x, y = y, x

        # xのサイズを更新
        self.par[x] += self.par[y]
        # yの親をxに変更
        self.par[y] = x

        return


N, M = map(int, input().split())
A, B = [], []
for _ in range(M):
    a, b = map(int, input().split())
    # インデックスをずらす
    A.append(a-1)
    B.append(b-1)

uni = UnionFind(N)

ans = [N * (N-1) // 2]
for i in range(M-1, 0, -1):
    ans.append(ans[-1])
    # 繋がっていないグループがつながったとき
    if uni.root(A[i]) != uni.root(B[i]):
        ans[-1] -= uni.size(A[i]) * uni.size(B[i])
        uni.connect(A[i], B[i])

for item in reversed(ans):
    print(item)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A, B = [], []
g = {}
for i in range(1, N+1):
    g[i] = []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    g[a].append(b)
    g[b].append(a)


def dfs(graph, start):
    visited = []
    stack = []
    stack.append(start)
    result = []
    while len(stack) > 0:
        next = stack.pop()
        if next in visited:
            continue
        result.append(next)
        visited.append(next)
        for nei in graph[next]:
            stack.append(nei)
    return result


for i in range(M):
    ans = 0
    g[A[i]].remove(B[i])
    g[B[i]].remove(A[i])
    for j in range(1, N+1):
        for k in range(j, N+1):
            if k not in dfs(g, j):
                ans += 1
    print(ans)


Fixed submission:
class UnionFind():
    # 初期化
    # 全てのノードの親は -1 とする
    def __init__(self, n):
        self.par = [-1] * n

    # xがどのグループに属しているか調べる
    def root(self, x):
        # xが親のとき
        if self.par[x] < 0:
            return x
        # xの親がさらに親をもつとき、それをxの親とする
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    # 自分のいるグループの頂点数を調べる
    def size(self, x):
        return -self.par[self.root(x)]

    # xとyをくっつける
    def connect(self, x, y):
        x = self.root(x)
        y = self.root(y)
        # すでにくっついていたらくっつけない
        if x == y:
            return

        # 大きい方(x)に小さい方(y)をくっつける
        if self.size(x) < self.size(y):
            x, y = y, x

        # xのサイズを更新
        self.par[x] += self.par[y]
        # yの親をxに変更
        self.par[y] = x

        return


N, M = map(int, input().split())
A, B = [], []
for _ in range(M):
    a, b = map(int, input().split())
    # インデックスをずらす
    A.append(a-1)
    B.append(b-1)

uni = UnionFind(N)

ans = [N * (N-1) // 2]
for i in range(M-1, 0, -1):
    ans.append(ans[-1])
    # 繋がっていないグループがつながったとき
    if uni.root(A[i]) != uni.root(B[i]):
        ans[-1] -= uni.size(A[i]) * uni.size(B[i])
        uni.connect(A[i], B[i])

for item in reversed(ans):
    print(item)