Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    c2[d1]+=1    
    if c2[d2]>0:
        c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
    if c2[d3]>0:
        c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
    q=[]
    for c2k,c2v in c2.items():
        if c2v==0:
            q.append(c2k)
    while q:
        del c2[q.pop()]            
#    print(c2)     
def q087_2(c2):
    c3=[]
    for c2k,c2v in c2.items():
        c3.append((c2k,c2k*c2v))

    c=0
#    for i in range(len(c3)):
    for i,c3i in enumerate(c3):
        c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
        for j,c3j in enumerate(c3[0:i]):
            c+=c3i[1]*c3j[1]
    return c,c2

cc=[]
c1=[1]*n
c2=defaultdict(int)
c2[1]=n
c=n    
pair=[i for i in range(n)]
for i in range(m-1):
#------------------------
    rta=root(a[m-i-1])
    rtb=root(b[m-i-1])
    if c1[rta]>=n or c1[rtb]>=n:
        cc.append(0)
        continue
    if rta<rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rta]+=c1[rtb]
        c1[rtb]=0
        d1=c1[rta]
#        pair[rtb]=rta
        unite(a[m-i-1],b[m-i-1])
    elif rta>rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rtb]+=c1[rta]
        c1[rta]=0
        d1=c1[rtb]
#        pair[rta]=rtb
        unite(a[m-i-1],b[m-i-1])
    else:
        cc.append(c)
        continue
#-------------------------------
    q087()

#    c3=[]
#    c=0
    c,c2=q087_2(c2)

    cc.append(c)
#-------------------------------

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)

Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    c2[d1]+=1    
    if c2[d2]>0:
        c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
    if c2[d3]>0:
        c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
    q=[]
    for c2k,c2v in c2.items():
        if c2v==0:
            q.append(c2k)
    while q:
        del c2[q.pop()]            
#    print(c2)     


cc=[]
c1=[1]*n
c2=defaultdict(int)
c2[1]=n
c=n    
pair=[i for i in range(n)]
for i in range(m-1):
#------------------------
    rta=root(a[m-i-1])
    rtb=root(b[m-i-1])
    if c1[rta]>=n or c1[rtb]>=n:
        cc.append(0)
        continue
    if rta<rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rta]+=c1[rtb]
        c1[rtb]=0
        d1=c1[rta]
#        pair[rtb]=rta
        unite(a[m-i-1],b[m-i-1])
    elif rta>rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rtb]+=c1[rta]
        c1[rta]=0
        d1=c1[rtb]
#        pair[rta]=rtb
        unite(a[m-i-1],b[m-i-1])
    else:
        cc.append(c)
        continue
#-------------------------------
    q087()

    c3=[]
    icnt=0
    for c2k,c2v in c2.items():
        c3.append((c2k,c2k*c2v))

    c=0
#    for i in range(len(c3)):
    for i,c3i in enumerate(c3):
        c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
        for j,c3j in enumerate(c3[0:i]):
            c+=c3i[1]*c3j[1]

    cc.append(c)
#-------------------------------

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

cc=[]
c1=[1]*n
c2=defaultdict(int)
c2[1]=n
c=n    
pair=[i for i in range(n)]
for i in range(m-1):
    rta=root(a[m-i-1])
    rtb=root(b[m-i-1])
    if c1[rta]>=n or c1[rtb]>=n:
        cc.append(0)
        continue
    if rta<rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rta]+=c1[rtb]
        c1[rtb]=0
        d1=c1[rta]
        pair[rtb]=rta
#        unite(a[m-i-1],b[m-i-1])
    elif rta>rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rtb]+=c1[rta]
        c1[rta]=0
        d1=c1[rtb]
        pair[rta]=rtb
#        unite(a[m-i-1],b[m-i-1])
    else:
        cc.append(c)
        continue

    c2[d1]+=1    
    if c2[d2]>0:
        c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
    if c2[d3]>0:
        c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
    q=[]
    for c2k,c2v in c2.items():
        if c2v==0:
            q.append(c2k)
    while q:
        del c2[q.pop()]            
#    print(c2)     
    c3=[]
    icnt=0
    for c2k,c2v in c2.items():
        c3.append((c2k,c2k*c2v))
    c=0
#    for i in range(len(c3)):
    for i,c3i in enumerate(c3):
        c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
        for j,c3j in enumerate(c3[0:i]):
            c+=c3i[1]*c3j[1]

#    for c2k,c2v in c3.items():
#        for c3k,c3v in c3.items():
#            if c2k==c3k:
#                c+=c2v*(c2v-c2k)//2
#            elif c2k>c3k:
#                c+=c2v*c3v
#    for c2k,c2v in c2.items():
#        for c3k,c3v in c2.items():
#            if c2k==c3k:
#                c+=(c2k**2)*c2v*(c2v-1)//2
#            elif c2k>c3k:
#                c+=c2k*c3k*c2v*c3v
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

cc=[]
c1=[1]*n
c2=defaultdict(int)
c2[1]=n
c=n    
pair=[i for i in range(n)]
for i in range(m-1):
    rta=root(a[m-i-1])
    rtb=root(b[m-i-1])
    if c1[rta]>=n or c1[rtb]>=n:
        cc.append(0)
        continue
    if rta<rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rta]+=c1[rtb]
        c1[rtb]=0
        d1=c1[rta]
        unite(a[m-i-1],b[m-i-1])
    elif rta>rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rtb]+=c1[rta]
        c1[rta]=0
        d1=c1[rtb]
        unite(a[m-i-1],b[m-i-1])
    else:
        cc.append(c)
        continue

    c2[d1]+=1    
    if c2[d2]>0:
        c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
    if c2[d3]>0:
        c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
    q=[]
    for c2k,c2v in c2.items():
        if c2v==0:
            q.append(c2k)
    while q:
        del c2[q.pop()]            
#    print(c2)     
    c3=[]
    icnt=0
    for c2k,c2v in c2.items():
        c3.append((c2k,c2k*c2v))
    c=0
#    for i in range(len(c3)):
    for i,c3i in enumerate(c3):
        c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
        for j,c3j in enumerate(c3[0:i]):
            c+=c3i[1]*c3j[1]

#    for c2k,c2v in c3.items():
#        for c3k,c3v in c3.items():
#            if c2k==c3k:
#                c+=c2v*(c2v-c2k)//2
#            elif c2k>c3k:
#                c+=c2v*c3v
#    for c2k,c2v in c2.items():
#        for c3k,c3v in c2.items():
#            if c2k==c3k:
#                c+=(c2k**2)*c2v*(c2v-1)//2
#            elif c2k>c3k:
#                c+=c2k*c3k*c2v*c3v
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

cc=[]
c1=[1]*n
c2=defaultdict(int)
c2[1]=n
c=n    
pair=[i for i in range(n)]
for i in range(m-1):
    rta=root(a[m-i-1])
    rtb=root(b[m-i-1])
    if c1[rta]>=n or c1[rtb]>=n:
        cc.append(0)
        continue
    if rta<rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rta]+=c1[rtb]
        c1[rtb]=0
        d1=c1[rta]
        unite(a[m-i-1],b[m-i-1])
    elif rta>rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rtb]+=c1[rta]
        c1[rta]=0
        d1=c1[rtb]
        unite(a[m-i-1],b[m-i-1])
    else:
        cc.append(c)
        continue

    c2[d1]+=1    
    if c2[d2]>0:
        c2[d2]-=1
    if c2[d2]==0:
        del c2[d2]
    if c2[d3]>0:
        c2[d3]-=1
    if c2[d3]==0:
        del c2[d3]
#    print(c1)        
#    print(c2)     
#    q=[]
#    for c2k,c2v in c2.items():
#        if c2v==0:
#            q.append(c2k)
#    while q:
#        del c2[q.pop()]            
#    print(c2)     
    c3=[]
    icnt=0
    for c2k,c2v in c2.items():
        c3.append((c2k,c2k*c2v))
    c=0
#    for i in range(len(c3)):
    for i,c3i in enumerate(c3):
        c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
        for j,c3j in enumerate(c3[0:i]):
            c+=c3i[1]*c3j[1]

#    for c2k,c2v in c3.items():
#        for c3k,c3v in c3.items():
#            if c2k==c3k:
#                c+=c2v*(c2v-c2k)//2
#            elif c2k>c3k:
#                c+=c2v*c3v
#    for c2k,c2v in c2.items():
#        for c3k,c3v in c2.items():
#            if c2k==c3k:
#                c+=(c2k**2)*c2v*(c2v-1)//2
#            elif c2k>c3k:
#                c+=c2k*c3k*c2v*c3v
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):

import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

cc=[]
c1=[1]*n
c2=defaultdict(int)
c2[1]=n
c=n    
pair=[i for i in range(n)]
for i in range(m-1):
    rta=root(a[m-i-1])
    rtb=root(b[m-i-1])
    if c1[rta]>=n or c1[rtb]>=n:
        cc.append(0)
        continue
    if rta<rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rta]+=c1[rtb]
        c1[rtb]=0
        d1=c1[rta]
        unite(a[m-i-1],b[m-i-1])
    elif rta>rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rtb]+=c1[rta]
        c1[rta]=0
        d1=c1[rtb]
        unite(a[m-i-1],b[m-i-1])
    else:
        cc.append(c)
        continue

    c2[d1]+=1    
    if c2[d2]>0:
        c2[d2]-=1
    if c2[d3]>0:
        c2[d3]-=1
#    print(c1)        
#    print(c2)     
    q=[]
    for c2k,c2v in c2.items():
        if c2v==0:
            q.append(c2k)
    while q:
        del c2[q.pop()]            
#    print(c2)     
    c3=[]
    icnt=0
    for c2k,c2v in c2.items():
        c3.append((c2k,c2k*c2v))
    c=0
#    for i in range(len(c3)):
    for i,c3i in enumerate(c3):
        c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
        for j,c3j in enumerate(c3[0:i]):
            c+=c3i[1]*c3j[1]

#    for c2k,c2v in c3.items():
#        for c3k,c3v in c3.items():
#            if c2k==c3k:
#                c+=c2v*(c2v-c2k)//2
#            elif c2k>c3k:
#                c+=c2v*c3v
#    for c2k,c2v in c2.items():
#        for c3k,c3v in c2.items():
#            if c2k==c3k:
#                c+=(c2k**2)*c2v*(c2v-1)//2
#            elif c2k>c3k:
#                c+=c2k*c3k*c2v*c3v
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

cc=[]
c1=[1]*n
c2=defaultdict(int)
c2[1]=n
c=n    
pair=[i for i in range(n)]
for i in range(m-1):
    rta=root(a[m-i-1])
    rtb=root(b[m-i-1])
    if c1[rta]>=n or c1[rtb]>=n:
        cc.append(0)
        continue
    if rta<rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rta]+=c1[rtb]
        c1[rtb]=0
        d1=c1[rta]
        unite(a[m-i-1],b[m-i-1])
    elif rta>rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rtb]+=c1[rta]
        c1[rta]=0
        d1=c1[rtb]
        unite(a[m-i-1],b[m-i-1])
    else:
        cc.append(c)
        continue

    c2[d1]+=1    
    if c2[d2]>0:
        c2[d2]-=1
    if c2[d3]>0:
        c2[d3]-=1
#    print(c1)        
#    print(c2)     
#    q=[]
#    for c2k,c2v in c2.items():
#        if c2v==0:
#            q.append(c2k)
#    while q:
#        del c2[q.pop()]            
#    print(c2)     
    c3=[]
    icnt=0
    for c2k,c2v in c2.items():
        if c2v!=0:
#            c3[c2k]=c2k*c2v
            c3.append((c2k,c2k*c2v))
    c=0
#    for i in range(len(c3)):
    for i,c3i in enumerate(c3):
        c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
        for j,c3j in enumerate(c3[0:i]):
            c+=c3i[1]*c3j[1]

#    for c2k,c2v in c3.items():
#        for c3k,c3v in c3.items():
#            if c2k==c3k:
#                c+=c2v*(c2v-c2k)//2
#            elif c2k>c3k:
#                c+=c2v*c3v
#    for c2k,c2v in c2.items():
#        for c3k,c3v in c2.items():
#            if c2k==c3k:
#                c+=(c2k**2)*c2v*(c2v-1)//2
#            elif c2k>c3k:
#                c+=c2k*c3k*c2v*c3v
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

cc=[]
c1=[1]*n
c2=defaultdict(int)
c2[1]=n
c=n    
pair=[i for i in range(n)]
for i in range(m-1):
    rta=root(a[m-i-1])
    rtb=root(b[m-i-1])
    if c1[rta]>=n or c1[rtb]>=n:
        cc.append(0)
        continue
    if rta<rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rta]+=c1[rtb]
        c1[rtb]=0
        d1=c1[rta]
        unite(a[m-i-1],b[m-i-1])
    elif rta>rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rtb]+=c1[rta]
        c1[rta]=0
        d1=c1[rtb]
        unite(a[m-i-1],b[m-i-1])
    else:
        cc.append(c)
        continue

    c2[d1]+=1    
    if c2[d2]>0:
        c2[d2]-=1
    if c2[d3]>0:
        c2[d3]-=1
#    print(c1)        
#    print(c2)     
#    q=[]
#    for c2k,c2v in c2.items():
#        if c2v==0:
#            q.append(c2k)
#    while q:
#        del c2[q.pop()]            
#    print(c2)     
    c3=[]
    icnt=0
    for c2k,c2v in c2.items():
        if c2v!=0:
#            c3[c2k]=c2k*c2v
            c3.append((c2k,c2k*c2v))
    c=0
    for i in range(len(c3)):
        c+=c3[i][1]*(c3[i][1]-c3[i][0])//2
        for j in range(i+1,len(c3)):
            c+=c3[i][1]*c3[j][1]

#    for c2k,c2v in c3.items():
#        for c3k,c3v in c3.items():
#            if c2k==c3k:
#                c+=c2v*(c2v-c2k)//2
#            elif c2k>c3k:
#                c+=c2v*c3v
#    for c2k,c2v in c2.items():
#        for c3k,c3v in c2.items():
#            if c2k==c3k:
#                c+=(c2k**2)*c2v*(c2v-1)//2
#            elif c2k>c3k:
#                c+=c2k*c3k*c2v*c3v
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

cc=[]
c1=[1]*n
c2=defaultdict(int)
c2[1]=n
c=n    
pair=[i for i in range(n)]
for i in range(m-1):
    rta=root(a[m-i-1])
    rtb=root(b[m-i-1])
    if c1[rta]>=n or c1[rtb]>=n:
        cc.append(0)
        continue
    if rta<rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rta]+=c1[rtb]
        c1[rtb]=0
        d1=c1[rta]
        unite(a[m-i-1],b[m-i-1])
    elif rta>rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rtb]+=c1[rta]
        c1[rta]=0
        d1=c1[rtb]
        unite(a[m-i-1],b[m-i-1])
    else:
        cc.append(c)
        continue

    c2[d1]+=1    
    if c2[d2]>0:
        c2[d2]-=1
    if c2[d3]>0:
        c2[d3]-=1
#    print(c1)        
#    print(c2)     
#    q=[]
#    for c2k,c2v in c2.items():
#        if c2v==0:
#            q.append(c2k)
#    while q:
#        del c2[q.pop()]            
#    print(c2)     
    c3=dict()
    for c2k,c2v in c2.items():
        if c2v!=0:
            c3[c2k]=c2k*c2v
 
    c=0
    for c2k,c2v in c3.items():
        for c3k,c3v in c3.items():
            if c2k==c3k:
                c+=c2v*(c2v-c2k)//2
            elif c2k>c3k:
                c+=c2v*c3v
#    for c2k,c2v in c2.items():
#        for c3k,c3v in c2.items():
#            if c2k==c3k:
#                c+=(c2k**2)*c2v*(c2v-1)//2
#            elif c2k>c3k:
#                c+=c2k*c3k*c2v*c3v
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

cc=[]
c1=[1]*n
c2=defaultdict(int)
c2[1]=n
c=n    
pair=[i for i in range(n)]
for i in range(m-1):
    rta=root(a[m-i-1])
    rtb=root(b[m-i-1])
    if c1[rta]>=n or c1[rtb]>=n:
        cc.append(0)
        continue
    if rta<rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rta]+=c1[rtb]
        c1[rtb]=0
        d1=c1[rta]
        unite(a[m-i-1],b[m-i-1])
    elif rta>rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rtb]+=c1[rta]
        c1[rta]=0
        d1=c1[rtb]
        unite(a[m-i-1],b[m-i-1])
    else:
        cc.append(c)
        continue

    c2[d1]+=1    
    if c2[d2]>0:
        c2[d2]-=1
    if c2[d3]>0:
        c2[d3]-=1
#    print(c1)        
#    print(c2)     
    q=[]
    for c2k,c2v in c2.items():
        if c2v==0:
            q.append(c2k)
    while q:
        del c2[q.pop()]            
#    print(c2)     
 
    c=0
#    for i0,i1 in combinations_with_replacement(c2.keys(),2):
#        if i0==i1:
#            c0=c2[i0]*(c2[i0]-1)//2
#            c+=(i0**2)*c0
#        else:
#            c+=i0*i1*c2[i0]*c2[i1]
    for c2k,c2v in c2.items():
        for c3k,c3v in c2.items():
            if c2k==c3k:
                c0=c2v*(c2v-1)//2
                c+=(c2k**2)*c0
            elif c2k>c3k:
                c+=c2k*c3k*c2v*c3v
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

cc=[]
c1=[1]*n
c2=defaultdict(int)
c2[1]=n
c=n    
pair=[i for i in range(n)]
for i in range(m-1):
    rta=root(a[m-i-1])
    rtb=root(b[m-i-1])
    if c1[rta]>=n or c1[rtb]>=n:
        cc.append(0)
        continue
    if rta<rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rta]+=c1[rtb]
        c1[rtb]=0
        d1=c1[rta]
        unite(a[m-i-1],b[m-i-1])
    elif rta>rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rtb]+=c1[rta]
        c1[rta]=0
        d1=c1[rtb]
        unite(a[m-i-1],b[m-i-1])
    else:
        cc.append(c)
        continue

    c2[d1]+=1    
    if c2[d2]>0:
        c2[d2]-=1
    if c2[d3]>0:
        c2[d3]-=1
    q=[]
    for c2k,c2v in c2.items():
        if c2v==0:
            q.append(c2k)
    while q:
        del c2[q.pop()]            
 
    c=0
    for i0,i1 in combinations_with_replacement(c2.keys(),2):
        if i0==i1:
            c0=c2[i0]*(c2[i0]-1)//2
            c+=(i0**2)*c0
        else:
            c+=i0*i1*c2[i0]*c2[i1]
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

cc=[]
c1=[1]*n
c2=defaultdict(int)
c2[1]=n
c=n    
pair=[i for i in range(n)]
for i in range(m-1):
    rta=root(a[m-i-1])
    rtb=root(b[m-i-1])
    if c1[rta]>=n or c1[rtb]>=n:
        cc.append(0)
        continue
    if rta<rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rta]+=c1[rtb]
        c1[rtb]=0
        d1=c1[rta]
        unite(a[m-i-1],b[m-i-1])
    elif rta>rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rtb]+=c1[rta]
        c1[rta]=0
        d1=c1[rtb]
        unite(a[m-i-1],b[m-i-1])
    else:
        cc.append(c)
        continue

    c2[d1]+=1    
    if c2[d2]>0:
        c2[d2]-=1
    if c2[d3]>0:
        c2[d3]-=1
#    print(c1)        
#    print(c2)     
    q=[]
    for c2k,c2v in c2.items():
        if c2v==0:
            q.append(c2k)
    while q:
        del c2[q.pop()]            
#    print(c2)     
 
    c=0
    for i0,i1 in combinations_with_replacement(c2.keys(),2):
        if i0==i1:
            c0=c2[i0]*(c2[i0]-1)//2
            c+=(i0**2)*c0
        else:
            c+=i0*i1*c2[i0]*c2[i1]
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

cc=[]
c1=[1]*n
    
pair=[i for i in range(n)]
for i in range(m-1):
    rta=root(a[m-i-1])
    rtb=root(b[m-i-1])
    if c1[rta]>=n or c1[rtb]>=n:
        cc.append(0)
        continue
    if rta<rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rta]+=c1[rtb]
        c1[rtb]=0
        d1=c1[rta]
        unite(a[m-i-1],b[m-i-1])
    elif rta>rtb:
        d2=c1[rta]
        d3=c1[rtb]
        c1[rtb]+=c1[rta]
        c1[rta]=0
        d1=c1[rtb]
        unite(a[m-i-1],b[m-i-1])

#    c2[d1]+=1    
#    if c2[d2]>0:
#        c2[d2]-=1
#    if c2[d3]>0:
#        c2[d3]-=1
 
    c2=dict()
    for c1ii in c1:
        if c1ii in c2.keys():
            c2[c1ii]=c2[c1ii]+1
        elif c1ii!=0:
            c2[c1ii]=1
#    print("c1:",c1)
#    print("c2:",c2)
    
    c=0
    for i0,i1 in combinations_with_replacement(c2.keys(),2):
        if i0==i1:
            c0=c2[i0]*(c2[i0]-1)//2
            c+=(i0**2)*c0
        else:
            c+=i0*i1*c2[i0]*c2[i1]
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
#input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

cc=[]
c1=[1]*n
pair=[i for i in range(n)]
for i in range(m-1):
    rta=root(a[m-i-1])
    rtb=root(b[m-i-1])
    if rta<rtb:
        c1[rta]+=c1[rtb]
        c1[rtb]=0
        unite(a[m-i-1],b[m-i-1])
    elif rta>rtb:
        c1[rtb]+=c1[rta]
        c1[rta]=0
        unite(a[m-i-1],b[m-i-1])

#    c1=[0]*n
#    for ii in range(n):
#        c1[root(ii)]+=1
    c2=dict()
    for c1ii in c1:
        if c1ii in c2.keys():
            c2[c1ii]=c2[c1ii]+1
        elif c1ii!=0:
            c2[c1ii]=1
    
    c=0
    for i0,i1 in combinations_with_replacement(c2.keys(),2):
        if i0==i1:
            c0=c2[i0]*(c2[i0]-1)//2
            c+=(i0**2)*c0
        else:
            c+=i0*i1*c2[i0]*c2[i1]
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Runtime Error):

import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

cc=[]
c1=[1]*n
pair=[i for i in range(n)]
for i in range(m-1):
    rb=root(b[m-i-1])
    crb=c1[rb]
    unite(a[m-i-1],b[m-i-1])
    c1[root(a[m-i-1])]+=crb
    c1[rb]=0

#    c1=[0]*n
#    for ii in range(n):
#        c1[root(ii)]+=1
    c2=dict()
    for c1ii in c1:
#    for ii in range(n):
#        c1ii=c1[ii]
        if c1ii in c2.keys():
            c2[c1ii]=c2[c1ii]+1
        elif c1ii!=0:
            c2[c1ii]=1
    print("c1:",c1)
    print("c2:",c2)
    
    c=0
    for i0,i1 in combinations_with_replacement(c2.keys(),2):
        if i0==i1:
            c0=c2[i0]*(c2[i0]-1)//2
            c+=(i0**2)*c0
        else:
            c+=i0*i1*c2[i0]*c2[i1]
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

cc=[]
pair=[i for i in range(n)]
for i in range(m-1):
    unite(a[m-i-1],b[m-i-1])

    c1=[0]*n
    for ii in range(n):
        c1[root(ii)]+=1
    c2=dict()
    for c1ii in c1:
#    for ii in range(n):
#        c1ii=c1[ii]
        if c1ii in c2.keys():
            c2[c1ii]=c2[c1ii]+1
        elif c1ii!=0:
            c2[c1ii]=1
#    print("c1:",c1)
#    print("c2:",c2)
    
    c=0
    for i0,i1 in combinations_with_replacement(c2.keys(),2):
        if i0==i1:
            c0=c2[i0]*(c2[i0]-1)//2
            c+=(i0**2)*c0
        else:
            c+=i0*i1*c2[i0]*c2[i1]
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product

icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

cc=[]
pair=[i for i in range(n)]
for i in range(m-1):
    unite(a[m-i-1],b[m-i-1])

    c1=[0]*n
    for ii in range(n):
        c1[root(ii)]+=1
    c2=dict()
    for c1ii in c1:
#    for ii in range(n):
#        c1ii=c1[ii]
        if c1ii in c2.keys():
            c2[c1ii]=c2[c1ii]+1
        elif c1ii!=0:
            c2[c1ii]=1
#    print("c1:",c1)
#    print("c2:",c2)
    
    c=0
    for i0,i1 in combinations_with_replacement(c2.keys(),2):
        if i0==i1:
            c0=c2[i0]*(c2[i0]-1)//2
            c+=(i0**2)*c0
        else:
            c+=i0*i1*c2[i0]*c2[i1]
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product

icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

cc=[]
pair=[i for i in range(n)]
for i in range(m-1):
    unite(a[m-i-1],b[m-i-1])

#    c1=[root(ii) for ii in range(n)]
#    c1=Counter(c1)
#    c2=[i for i in c1.values()]
#    c2=Counter(c2)

    c1=[0]*n
    for ii in range(n):
        c1[root(ii)]+=1
    c2=Counter(c1)
    del c2[0]
#    cmax=max(c1)    
#    c2=dict()
#    for ii in range(n):
#        if c1[ii] in c2.keys():
#            c2[c1[ii]]=c2[c1[ii]]+1
#        elif c1[ii]!=0:
#            c2[c1[ii]]=1
#    print("c1:",c1)
#    print("c2:",c2)
    
    c=0
    for i0,i1 in combinations_with_replacement(c2.keys(),2):
        if i0==i1:
            c0=c2[i0]*(c2[i0]-1)//2
            c+=(i0**2)*c0
        else:
            c+=i0*i1*c2[i0]*c2[i1]
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)

Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product

icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

cc=[]
pair=[i for i in range(n)]
for i in range(m-1):
    unite(a[m-i-1],b[m-i-1])

    c1=[0]*n
    for ii in range(n):
        c1[root(ii)]+=1
    cmax=max(c1)    
    c2=dict()
    for ii in range(n):
        if c1[ii] in c2.keys():
            c2[c1[ii]]=c2[c1[ii]]+1
        elif c1[ii]!=0:
            c2[c1[ii]]=1
#    print("c1:",c1)
#    print("c2:",c2)
    
    c=0
    for i0,i1 in combinations_with_replacement(c2.keys(),2):
        if i0==i1:
            c0=c2[i0]*(c2[i0]-1)//2
            c+=(i0**2)*c0
        else:
            c+=i0*i1*c2[i0]*c2[i1]
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product

icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

cc=[]
pair=[i for i in range(n)]
for i in range(m-1):
    unite(a[m-i-1],b[m-i-1])

    c1=[0]*n
    for ii in range(n):
        c1[root(ii)]+=1
    cmax=max(c1)    
    c2=dict()
    for ii in range(n):
        if c1[ii] in c2.keys():
            c2[c1[ii]]=c2[c1[ii]]+1
        else:
            c2[c1[ii]]=1
#    print("c1:",c1)
#    print("c2:",c2)
    
    c=0
    for i0,i1 in combinations_with_replacement(c2.keys(),2):
        if i0==i1:
            c0=c2[i0]*(c2[i0]-1)//2
            c+=(i0**2)*c0
        else:
            c+=i0*i1*c2[i0]*c2[i1]
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product

icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

cc=[]
pair=[i for i in range(n)]
for i in range(m-1):
    unite(a[m-i-1],b[m-i-1])

    l=[root(ii) for ii in range(n)]
    l.sort()
    l=Counter(l)
    ll=[i for i in l.values()]
    ll.sort()
    ll=Counter(ll)
#    print("ll",ll)
    llv=[i for i in ll.values()]
    llk=[i for i in ll.keys()]
#    print("llv",llv)
    
    c=0
    for i in combinations_with_replacement(llk,2):
        if i[0]==i[1]:
            c0=ll[i[0]]*(ll[i[0]]-1)//2
            c+=(i[0]**2)*c0
        else:
            c+=i[0]*i[1]*ll[i[0]]*ll[i[1]]
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product

icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

cc=[]
pair=[i for i in range(n)]
for i in range(m-1):
    unite(a[m-i-1],b[m-i-1])

    l=[root(ii) for ii in range(n)]
    l.sort()
    l=Counter(l)
    ll=[i for i in l.values()]
    ll.sort()
    ll=Counter(ll)
#    print("ll",ll)
    llv=[i for i in ll.values()]
    llk=[i for i in ll.keys()]
#    print("llv",llv)
    
    c=0
    for i in combinations_with_replacement(llk,2):
        if i[0]==i[1]:
            c0=ll[i[0]]*(ll[i[0]]-1)//2
            c+=(i[0]**2)*c0
        else:
            c+=i[0]*i[1]*ll[i[0]]*ll[i[1]]
    cc.append(c)

for i in range(m-2,-1,-1):
    print(cc[i])
print(n*(n-1)//2)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product

icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

for i in range(m):
    pair=[i for i in range(n)]
    for ii in range(i+1,m):
        unite(a[ii],b[ii])

#    l=[root(ii) for ii in range(n)]
#    l.sort()
    print(l[0])


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product

icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

for i in range(m):
    pair=[i for i in range(n)]
    for ii in range(i+1,m):
        unite(a[ii],b[ii])

    l=[root(ii) for ii in range(n)]
    l.sort()
    l=Counter(l)
    ll=[i for i in l.values()]
    ll.sort()
    ll=Counter(ll)
#    print("ll",ll)
    llv=[i for i in ll.values()]
    llk=[i for i in ll.keys()]
#    print("llv",llv)
    
    c=0
    for i in combinations_with_replacement(llk,2):
        if i[0]==i[1]:
            c0=ll[i[0]]*(ll[i[0]]-1)//2
            c+=(i[0]**2)*c0
        else:
            c+=i[0]*i[1]*ll[i[0]]*ll[i[1]]
    print(c)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product

icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

for i in range(m):
    pair=[i for i in range(n)]
    for ii in range(i+1,m):
        unite(a[ii],b[ii])

    l=[root(ii) for ii in range(n)]
    l.sort()
    l=Counter(l)
    ll=[i for i in l.values()]
    ll.sort()
    ll=Counter(ll)
#    print("ll",ll)
    llv=[i for i in ll.values()]
    llk=[i for i in ll.keys()]
#    print("llv",llv)
    
    c=0
    for i in combinations_with_replacement(llk,2):
        if i[0]==i[1]:
            c0=ll[i[0]]*(ll[i[0]]-1)//2
            c+=(i[0]**2)*c0
        else:
            c+=i[0]*i[1]*ll[i[0]]*ll[i[1]]
    print(c)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product

icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

for i in range(m):
    pair=[i for i in range(n)]
    for ii in range(i+1,m):
        unite(a[ii],b[ii])

    l=[root(ii) for ii in range(n)]
    l.sort()
    l=Counter(l)
    ll=[i for i in l.values()]
    ll.sort()
    ll=Counter(ll)
#    print("ll",ll)
    llv=[i for i in ll.values()]
    llk=[i for i in ll.keys()]
#    print("llv",llv)
    
    c=0
    for i in combinations_with_replacement(llk,2):
        if i[0]==i[1]:
            c0=ll[i[0]]*(ll[i[0]]-1)//2
            c+=(i[0]**2)*c0
        else:
            c+=i[0]*i[1]*ll[i[0]]*ll[i[1]]
    print(c)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import combinations

n,m=map(int,input().split())
pair=[i for i in range(n)]
a=[0]*m
b=[0]*m
for i in range(m):
    ai,bi=map(int,input().split())
    a[i]=ai-1
    b[i]=bi-1

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

for i in range(m):
    pair=[i for i in range(n)]
    for ii in range(i+1,m):
        unite(a[ii],b[ii])

#    print(pair)
    l=[root(ii) for ii in range(n)]
#    print(i,l)
    l.sort()
    l=Counter(l)
    ll=[i for i in l.values()]
#    lenl=len(l)
#    print(ll)
#    ll=l.most_common()
    c=0
    for i in combinations(ll,2):
        c+=i[0]*i[1]
    print(c)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict
input = sys.stdin.readline
    
icase=0
if icase==0:
    n,m=map(int,input().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ai,bi=map(int,input().split())
        a[i]=ai-1
        b[i]=bi-1
elif icase==1:
    n,m=4,5
    a=[0, 2, 0, 1, 0]
    b=[1, 3, 2, 2, 3]
elif icase==2:
    n,m=6,5
    a=[1, 0, 4, 2, 3]
    b=[2, 1, 5, 3, 4]
elif icase==3:
    n,m=26,25
    a=[13, 13, 7, 1, 20, 0, 2, 3, 5, 13, 0, 0, 16, 3, 1, 15, 13, 13, 16, 9, 13, 8, 12, 6, 8]
    b=[14, 18, 25, 20, 24, 19, 13, 13, 21, 22, 14, 4, 23, 25, 10, 17, 17, 20, 20, 14, 21, 9, 22, 9, 11]
elif icase==4:
    f=open(r"C:\Users\nishi\999atcoder\q100\q087\testcase_01_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        ll=f.readline()
        ai,bi=map(int,ll.split())
        a[i]=ai-1
        b[i]=bi-1
    f.close()

pair=[i for i in range(n)]

def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x

def q087():
    cc=[]
    c1=[1]*n
    c2=defaultdict(int)
    c2[1]=n
    c=n    
#    pair=[i for i in range(n)]
    for i in range(m-1):
#------------------------
        rta=root(a[m-i-1])
        rtb=root(b[m-i-1])
        if c1[rta]>=n or c1[rtb]>=n:
            cc.append(0)
            continue
        if rta<rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rta]+=c1[rtb]
            c1[rtb]=0
            d1=c1[rta]
#        pair[rtb]=rta
            unite(a[m-i-1],b[m-i-1])
        elif rta>rtb:
            d2=c1[rta]
            d3=c1[rtb]
            c1[rtb]+=c1[rta]
            c1[rta]=0
            d1=c1[rtb]
#        pair[rta]=rtb
            unite(a[m-i-1],b[m-i-1])
        else:
            cc.append(c)
            continue

        c2[d1]+=1    
        if c2[d2]>0:
            c2[d2]-=1
#    if c2[d2]==0:
#        del c2[d2]
        if c2[d3]>0:
            c2[d3]-=1
#    if c2[d3]==0:
#        del c2[d3]
#    print(c1)        
#    print(c2)     
        q=[]
        for c2k,c2v in c2.items():
            if c2v==0:
                q.append(c2k)
        while q:
            del c2[q.pop()]            
#    print(c2)     
        c3=[]
        for c2k,c2v in c2.items():
            c3.append((c2k,c2k*c2v))

        c=0
#    for i in range(len(c3)):
        for i,c3i in enumerate(c3):
            c+=c3i[1]*(c3i[1]-c3i[0])//2
#        for j in range(i+1,len(c3)):
            for j,c3j in enumerate(c3[0:i]):
                c+=c3i[1]*c3j[1]
        cc.append(c)

    for i in range(m-2,-1,-1):
        print(cc[i])
    print(n*(n-1)//2)
#-------------------------------
q087()
#-------------------------------