Buggy python submission (verdict: Time Limit Exceeded):
#要素の根を探す関数
def find_root(n):
    while(parts[n-1][0]!=n-1):
        n=parts[n-1][0]+1
    return tuple(parts[n-1])

#入力を受け取る
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]

#partsの1つ目は根の番号、2つ目は深さ、3つ目は接続されている要素数
parts=[[i,1,1] for i in range(N)]
#全部壊れた時の不便度はN(N-1)
ans=[N*(N-1)//2]

#橋の数-1だけ処理を行う（橋が全部かかっているときは不便度0なので）
for i in range(M-1):
#一番最後に壊れた橋を探す
    ab=AB.pop()
#それぞれの要素の根を探す
    a=find_root(ab[0])
    b=find_root(ab[1])
#木構造が浅い方をaとする
    if a[1]<=b[1]:
        a,b=a,b
    else:
        b,a=a,b
#根が同一ならば処理不要
    if a[0]==b[0]:
        ans.append(ans[-1])
#根が違うのであれば、以後木をくっつける処理を行う
    else:
#要素x個の木と要素y個の木が繋がれば不便度はxyだけ減る
        ans.append(ans[-1]-a[2]*b[2])
#bの根にaを接続する
        parts[b[0]][0]=parts[a[0]][0]
#接続後のaの深さは(aの深さ)と(bの深さ+1)の大きい方
        parts[a[0]][1]=max(parts[a[0]][1],parts[b[0]][1]+1)
#aの要素数+bの要素数が接続後のaの要素数
        parts[a[0]][2]+=parts[b[0]][2]
#答えを出力
for i in reversed(ans):
    print(i)

Fixed submission:
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(M)]
parts=[i for i in range(N)]
ans=[N*(N-1)//2]
parts_dict=dict([[i,[i]] for i in range(N)])

for i in range(M-1):
    ab=AB.pop()
    if parts[ab[0]-1]==parts[ab[1]-1]:
        ans.append(ans[-1])
    else:
        a,b=sorted(ab,key=lambda x:parts[x-1])
        len_a,len_b=len(parts_dict[parts[a-1]]),len(parts_dict[parts[b-1]])
        ans.append(ans[-1]-len_a*len_b)
        parts_dict[parts[a-1]]+=parts_dict[parts[b-1]]
        for i in parts_dict[parts[b-1]]:
            parts[i]=parts[a-1]

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

Buggy python submission (verdict: Time Limit Exceeded):
#要素の根を探す関数
def find_root(n):
    while(parts[n-1][0]!=n-1):
        n=parts[n-1][0]+1
    return tuple(parts[n-1])

#入力を受け取る
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]

#partsの1つ目は根の番号、2つ目は深さ、3つ目は接続されている要素数
parts=[[i,1,1] for i in range(N)]
#全部壊れた時の不便度はN(N-1)
ans=[N*(N-1)//2]

#橋の数-1だけ処理を行う（橋が全部かかっているときは不便度0なので）
for i in range(M-1):
#一番最後に壊れた橋を探す
    ab=AB.pop()
#それぞれの要素の根を探す
    a=find_root(ab[0])
    b=find_root(ab[1])
#木構造が浅い方をaとする
    if a[1]<=b[1]:
        a,b=a,b
    else:
        b,a=a,b
#根が同一ならば処理不要
    if a[0]==b[0]:
        ans.append(ans[-1])
#根が違うのであれば、以後木をくっつける処理を行う
    else:
#要素x個の木と要素y個の木が繋がれば不便度はxyだけ減る
        ans.append(ans[-1]-a[2]*b[2])
#bの根にaを接続する
        parts[b[0]][0]=parts[a[0]][0]
#接続後のaの深さは(aの深さ)と(bの深さ+1)の大きい方
        parts[a[0]][1]=max(parts[a[0]][1],parts[b[0]][1]+1)
#aの要素数+bの要素数が接続後のaの要素数
        parts[a[0]][2]+=parts[b[0]][2]
#答えを出力
for i in reversed(ans):
    print(i)

Fixed submission:
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(M)]
parts=[i for i in range(N)]
ans=[N*(N-1)//2]
parts_dict=dict([[i,[i]] for i in range(N)])

for i in range(M-1):
    ab=AB.pop()
    if parts[ab[0]-1]==parts[ab[1]-1]:
        ans.append(ans[-1])
    else:
        a,b=sorted(ab,key=lambda x:parts[x-1])
        len_a,len_b=len(parts_dict[parts[a-1]]),len(parts_dict[parts[b-1]])
        ans.append(ans[-1]-len_a*len_b)
        parts_dict[parts[a-1]]+=parts_dict[parts[b-1]]
        for i in parts_dict[parts[b-1]]:
            parts[i]=parts[a-1]

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