Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
cango=dict()
res=[0]
data=[0 for _ in range(1+n)]
def calc(k):
    return 1/2*k*(k-1)

def search(data,x):
    if data[x]<=0:
        return x
    else:
        data[x]=search(data,data[x])
    return data[x]

for i in range(m):
    a,b=branch.pop()
    aset={a,}
    bset={b,}
    aroot=search(data,a)
    aidx=data[aroot]
    broot=search(data,b)
    bidx=data[broot]
    if aidx!=0:aset=cango[aidx]
    if bidx!=0:bset=cango[bidx]
    lena=len(aset)
    lenb=len(bset)
    if aidx==0 and bidx==0:
        data[a]=-1*a
        data[b]=a
        cango[-1*a]={a,b}
    elif aidx==bidx and aidx!=0:
        res.append(res[-1])
        continue
    elif aidx==0 and bidx!=0:
        cango[bidx]|={a,}
        data[a]=broot
    elif aidx!=0 and bidx==0:
        cango[aidx]|={b,}
        data[b]=aroot
    elif aidx!=0 and bidx!=0 and aidx!=bidx:
        cango.pop(bidx)
        cango[aidx]|=bset
        data[broot]=aroot
    res.append(res[-1]-calc(lena)-calc(lenb)+calc(lena+lenb))

for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

Fixed submission:
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
res=[0]
data=[-1 for _ in range(1+n)]
def calc(k):
    k=abs(k)
    return 1/2*k*(k-1)

def search(data,x):
    if data[x]<=0:
        return x
    else:
        data[x]=search(data,data[x])
    return data[x]

for i in range(m):
    a,b=branch.pop()
    aroot=search(data,a)
    broot=search(data,b)
    if aroot==broot:
        res.append(res[-1])
        continue
    res.append(res[-1]-calc(data[aroot])-calc(data[broot])+calc(data[aroot]+data[broot]))
    if data[aroot]<=data[broot]:
        data[aroot]+=data[broot]
        data[broot]=aroot
    elif data[aroot]>data[broot]:
        data[broot]+=data[aroot]
        data[aroot]=broot
for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
cango=dict()
res=[0]
data=[0 for _ in range(1+n)]

def calc(k):
    return 1/2*k*(k-1)

def search(data,x):
    if data[x]<=0:
        return x,data[x]
    else:
        x,data[x]=search(data,data[x])
    return x,data[x]

for i in range(m):
    a,b=branch.pop()
    aset={a,}
    bset={b,}
    aroot,aidx=search(data,a)
    broot,bidx=search(data,b)
    if aidx!=0:aset=cango[aidx]
    if bidx!=0:bset=cango[bidx]
    lena=len(aset)
    lenb=len(bset)
    if aidx==0 and bidx==0:
        data[a]=-1*a
        data[b]=a
        cango[-1*a]={a,b}
    elif aidx==bidx and aidx!=0:
        res.append(res[-1])
        continue
    elif aidx==0 and bidx!=0:
        cango[bidx]|={a,}
        data[a]=broot
    elif aidx!=0 and bidx==0:
        cango[aidx]|={b,}
        data[b]=aroot
    elif aidx!=0 and bidx!=0 and aidx!=bidx:
        cango.pop(bidx)
        cango[aidx]|=bset
        data[broot]=aroot
    res.append(res[-1]-calc(lena)-calc(lenb)+calc(lena+lenb))

for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

Fixed submission:
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
res=[0]
data=[-1 for _ in range(1+n)]
def calc(k):
    k=abs(k)
    return 1/2*k*(k-1)

def search(data,x):
    if data[x]<=0:
        return x
    else:
        data[x]=search(data,data[x])
    return data[x]

for i in range(m):
    a,b=branch.pop()
    aroot=search(data,a)
    broot=search(data,b)
    if aroot==broot:
        res.append(res[-1])
        continue
    res.append(res[-1]-calc(data[aroot])-calc(data[broot])+calc(data[aroot]+data[broot]))
    if data[aroot]<=data[broot]:
        data[aroot]+=data[broot]
        data[broot]=aroot
    elif data[aroot]>data[broot]:
        data[broot]+=data[aroot]
        data[aroot]=broot
for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
cango=dict()
res=[0]
data=[0 for _ in range(1+n)]

def calc(k):
    return 1/2*k*(k-1)

def search(data,x):
    bef=x
    while data[x]>0:
        data[bef]=data[x]
        bef=x
        x=data[x]
    return x,data[x]

for i in range(m):
    a,b=branch.pop()
    aset={a,}
    bset={b,}
    aroot,aidx=search(data,a)
    broot,bidx=search(data,b)
    if aidx!=0:aset=cango[aidx]
    if bidx!=0:bset=cango[bidx]
    lena=len(aset)
    lenb=len(bset)
    if aidx==0 and bidx==0:
        data[a]=-1*a
        data[b]=a
        cango[-1*a]={a,b}
    elif aidx==bidx and aidx!=0:
        res.append(res[-1])
        continue
    elif aidx==0 and bidx!=0:
        cango[bidx]|={a,}
        data[a]=broot
    elif aidx!=0 and bidx==0:
        cango[aidx]|={b,}
        data[b]=aroot
    elif aidx!=0 and bidx!=0 and aidx!=bidx:
        cango.pop(bidx)
        cango[aidx]|=bset
        data[broot]=aroot
    res.append(res[-1]-calc(lena)-calc(lenb)+calc(lena+lenb))

for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

Fixed submission:
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
res=[0]
data=[-1 for _ in range(1+n)]
def calc(k):
    k=abs(k)
    return 1/2*k*(k-1)

def search(data,x):
    if data[x]<=0:
        return x
    else:
        data[x]=search(data,data[x])
    return data[x]

for i in range(m):
    a,b=branch.pop()
    aroot=search(data,a)
    broot=search(data,b)
    if aroot==broot:
        res.append(res[-1])
        continue
    res.append(res[-1]-calc(data[aroot])-calc(data[broot])+calc(data[aroot]+data[broot]))
    if data[aroot]<=data[broot]:
        data[aroot]+=data[broot]
        data[broot]=aroot
    elif data[aroot]>data[broot]:
        data[broot]+=data[aroot]
        data[aroot]=broot
for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
cango=dict()
res=[0]
data=[0 for _ in range(1+n)]

def calc(k):
    return 1/2*k*(k-1)

def search(data,x):
    bef=x
    while data[x]>0:
        data[bef]=data[x]
        bef=x
        x=data[x]
    return x,data[x]

for i in range(m):
    a,b=branch.pop()
    aroot,aidx=search(data,a)
    broot,bidx=search(data,b)
    if aidx!=0:aset=cango[aidx]
    if bidx!=0:bset=cango[bidx]
    lena=len(aset)
    lenb=len(bset)
    if aidx==0 and bidx==0:
        data[a]=-1*a
        data[b]=a
        cango[-1*a]={a,b}
    elif aidx==bidx and aidx!=0:
        res.append(res[-1])
        continue
    elif aidx==0 and bidx!=0:
        cango[bidx]|={a,}
        data[a]=broot
    elif aidx!=0 and bidx==0:
        cango[aidx]|={b,}
        data[b]=aroot
    elif aidx!=0 and bidx!=0 and aidx!=bidx:
        cango.pop(bidx)
        cango[aidx]|=bset
        data[broot]=aroot
    res.append(res[-1]-calc(lena)-calc(lenb)+calc(lena+lenb))

for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

Fixed submission:
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
res=[0]
data=[-1 for _ in range(1+n)]
def calc(k):
    k=abs(k)
    return 1/2*k*(k-1)

def search(data,x):
    if data[x]<=0:
        return x
    else:
        data[x]=search(data,data[x])
    return data[x]

for i in range(m):
    a,b=branch.pop()
    aroot=search(data,a)
    broot=search(data,b)
    if aroot==broot:
        res.append(res[-1])
        continue
    res.append(res[-1]-calc(data[aroot])-calc(data[broot])+calc(data[aroot]+data[broot]))
    if data[aroot]<=data[broot]:
        data[aroot]+=data[broot]
        data[broot]=aroot
    elif data[aroot]>data[broot]:
        data[broot]+=data[aroot]
        data[aroot]=broot
for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
cango=dict()
res=[0]
data=[0 for _ in range(1+n)]
def calc(k):
    return 1/2*k*(k-1)
def search(data,x):
    while data[x]>0:
        x=data[x]
    return x,data[x]
for i in range(m):
    a,b=branch.pop()
    aset={a,}
    bset={b,}
    aroot,aidx=search(data,a)
    broot,bidx=search(data,b)
    if aidx!=0:aset=cango[aidx]
    if bidx!=0:bset=cango[bidx]
    lena=len(aset)
    lenb=len(bset)
    if aidx==0 and bidx==0:
        data[a]=-1*a
        data[b]=a
        cango[-1*a]={a,b}
    elif aidx==bidx and aidx!=0:
        res.append(res[-1])
        continue
    elif aidx==0 and bidx!=0:
        cango[bidx]|={a,}
        data[a]=broot
    elif aidx!=0 and bidx==0:
        cango[aidx]|={b,}
        data[b]=aroot
    elif aidx!=0 and bidx!=0 and aidx!=bidx:
        cango.pop(bidx)
        cango[aidx]|=bset
        data[broot]=aroot
    res.append(res[-1]-calc(lena)-calc(lenb)+calc(lena+lenb))

for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

Fixed submission:
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
res=[0]
data=[-1 for _ in range(1+n)]
def calc(k):
    k=abs(k)
    return 1/2*k*(k-1)

def search(data,x):
    if data[x]<=0:
        return x
    else:
        data[x]=search(data,data[x])
    return data[x]

for i in range(m):
    a,b=branch.pop()
    aroot=search(data,a)
    broot=search(data,b)
    if aroot==broot:
        res.append(res[-1])
        continue
    res.append(res[-1]-calc(data[aroot])-calc(data[broot])+calc(data[aroot]+data[broot]))
    if data[aroot]<=data[broot]:
        data[aroot]+=data[broot]
        data[broot]=aroot
    elif data[aroot]>data[broot]:
        data[broot]+=data[aroot]
        data[aroot]=broot
for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
cango=dict()
res=[0]
data=[0 for _ in range(1+n)]
def calc(k):
    return 1/2*k*(k-1)
def search(data,x):
    while data[x]>0:
        x=data[x]
    return x,data[x]
for i in range(m):
    a,b=branch.pop()
    aset={a,}
    bset={b,}
    aroot,aidx=search(data,a)
    broot,bidx=search(data,b)
    if aidx!=0:aset=cango[aidx]
    if bidx!=0:bset=cango[bidx]
    lena=len(aset)
    lenb=len(bset)
    if aidx==0 and bidx==0:
        data[a]=-1*a
        data[b]=a
        cango[-1*a]={a,b}
    elif aidx==bidx:
        res.append(res[-1])
        continue
    elif aidx==0 and bidx!=0:
        cango[bidx]|={a,}
        data[a]=bidx
    elif aidx!=0 and bidx==0:
        cango[aidx]|={b,}
        data[b]=aidx
    elif aidx!=0 and bidx!=0 and aidx!=bidx:
        cango.pop(aidx)
        cango.pop(bidx)
        cango[aidx]=aset|bset
        data[broot]=aroot
    res.append(res[-1]-calc(lena)-calc(lenb)+calc(lena+lenb))

for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

Fixed submission:
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
res=[0]
data=[-1 for _ in range(1+n)]
def calc(k):
    k=abs(k)
    return 1/2*k*(k-1)

def search(data,x):
    if data[x]<=0:
        return x
    else:
        data[x]=search(data,data[x])
    return data[x]

for i in range(m):
    a,b=branch.pop()
    aroot=search(data,a)
    broot=search(data,b)
    if aroot==broot:
        res.append(res[-1])
        continue
    res.append(res[-1]-calc(data[aroot])-calc(data[broot])+calc(data[aroot]+data[broot]))
    if data[aroot]<=data[broot]:
        data[aroot]+=data[broot]
        data[broot]=aroot
    elif data[aroot]>data[broot]:
        data[broot]+=data[aroot]
        data[aroot]=broot
for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
cango=[]
res=[0]
def calc(k):
    return 1/2*k*(k-1)
for i in range(m):
    a,b=branch.pop()
    aset={a,}
    bset={b,}
    aflag,bflag=False,False
    for x in cango:
        if aflag==True and bflag==True:break
        if a in x:
            aset=x
            aflag=True
        if b in x:
            bset=x
            bflag=True
    if aset==bset:
        res.append(res[-1])
        continue
    if aset in cango:cango.remove(aset)
    if bset in cango:cango.remove(bset)
    cango.append(aset|bset)
    res.append(res[-1]-calc(len(aset))-calc(len(bset))+calc(len(aset)+len(bset)))

for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

Fixed submission:
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
res=[0]
data=[-1 for _ in range(1+n)]
def calc(k):
    k=abs(k)
    return 1/2*k*(k-1)

def search(data,x):
    if data[x]<=0:
        return x
    else:
        data[x]=search(data,data[x])
    return data[x]

for i in range(m):
    a,b=branch.pop()
    aroot=search(data,a)
    broot=search(data,b)
    if aroot==broot:
        res.append(res[-1])
        continue
    res.append(res[-1]-calc(data[aroot])-calc(data[broot])+calc(data[aroot]+data[broot]))
    if data[aroot]<=data[broot]:
        data[aroot]+=data[broot]
        data[broot]=aroot
    elif data[aroot]>data[broot]:
        data[broot]+=data[aroot]
        data[aroot]=broot
for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
cango=[]
res=[0]
def calc(k):
    return 1/2*k*(k-1)
for i in range(m):
    a,b=branch.pop()
    aset={a,}
    bset={b,}
    for i,x in enumerate(cango):
        if a in x:aset=x
        if b in x:bset=x
    if aset==bset:
        res.append(res[-1])
        continue
    if aset in cango:cango.remove(aset)
    if bset in cango:cango.remove(bset)
    cango.append(aset|bset)
    res.append(res[-1]-calc(len(aset))-calc(len(bset))+calc(len(aset)+len(bset)))

for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

Fixed submission:
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
res=[0]
data=[-1 for _ in range(1+n)]
def calc(k):
    k=abs(k)
    return 1/2*k*(k-1)

def search(data,x):
    if data[x]<=0:
        return x
    else:
        data[x]=search(data,data[x])
    return data[x]

for i in range(m):
    a,b=branch.pop()
    aroot=search(data,a)
    broot=search(data,b)
    if aroot==broot:
        res.append(res[-1])
        continue
    res.append(res[-1]-calc(data[aroot])-calc(data[broot])+calc(data[aroot]+data[broot]))
    if data[aroot]<=data[broot]:
        data[aroot]+=data[broot]
        data[broot]=aroot
    elif data[aroot]>data[broot]:
        data[broot]+=data[aroot]
        data[aroot]=broot
for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
cango=[]
res=[0]
for i in range(m):
    aidx=-1
    bidx=-1
    a,b=branch.pop()
    for i,x in enumerate(cango):
        if a in x:aidx=i
        if b in x:bidx=i
    if aidx==-1 and bidx==-1:cango.append({a,b,})
    elif aidx==-1 and bidx!=-1:cango[bidx]|={a,}
    elif aidx!=-1 and bidx==-1:cango[aidx]|={b,}
    elif aidx!=bidx:
        aset=cango[aidx]
        bset=cango[bidx]
        cango.pop(aidx)
        if aidx<bidx:cango.pop(bidx-1)
        elif aidx>bidx:cango.pop(bidx)
        cango.append(aset|bset)
    now=0
    for x in cango:
        now+=1/2*len(x)*(len(x)-1)
    res.append(now)

for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

Fixed submission:
n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
res=[0]
data=[-1 for _ in range(1+n)]
def calc(k):
    k=abs(k)
    return 1/2*k*(k-1)

def search(data,x):
    if data[x]<=0:
        return x
    else:
        data[x]=search(data,data[x])
    return data[x]

for i in range(m):
    a,b=branch.pop()
    aroot=search(data,a)
    broot=search(data,b)
    if aroot==broot:
        res.append(res[-1])
        continue
    res.append(res[-1]-calc(data[aroot])-calc(data[broot])+calc(data[aroot]+data[broot]))
    if data[aroot]<=data[broot]:
        data[aroot]+=data[broot]
        data[broot]=aroot
    elif data[aroot]>data[broot]:
        data[broot]+=data[aroot]
        data[aroot]=broot
for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))