Problem p03108 (python)

Fixed submission:
import sys
sys.setrecursionlimit(100000)

n, m=map(int, input().split())
a=[0 for i in range(m)]
b=[0 for i in range(m)]
g=[list() for i in range(1+n)]
#print(g)

par=[i for i in range(n)]
cnt_con=[1 for i in range(n)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
def connect(x,y):
    #par[x]=root(x)
    #par[y]=root(y)
    if root(x)==root(y):
        0
    else:
        cnt_con[root(y)]+=cnt_con[root(x)]
        par[root(x)]=root(y)      
    return

for i in range(m):
    a[i], b[i]=map(int, input().split())
    a[i], b[i]=a[i]-1, b[i]-1


tmp=int(n*(n-1)/2)
ans=[0]*m
ans[-1]=tmp
#ans[0]=0
#print('a,b=',a,b)
for i in range(m-1,-1,-1):
    ans[i]=tmp
    if root(a[i])==root(b[i]):
        0
    else:
        tmp-=cnt_con[root(a[i])]*cnt_con[root(b[i])]
    connect(a[i],b[i])
    #print('i,tmp',i,(a[i],b[i]),ans[i],tmp,par,cnt_con)
    

    
for i in range(m):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
sys.setrecursionlimit(100000)

n, m=map(int, input().split())
a=[0 for i in range(m)]
b=[0 for i in range(m)]
g=[list() for i in range(1+n)]
#print(g)

par=[i for i in range(n)]
cnt_con=[1 for i in range(n)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
def connect(x,y):
    #par[x]=root(x)
    #par[y]=root(y)
    if root(x)==root(y):
        0
    else:
        cnt_con[root(y)]+=cnt_con[root(x)]
        par[root(x)]=root(y)      
    return

for i in range(m):
    a[i], b[i]=map(int, input().split())
    a[i], b[i]=a[i]-1, b[i]-1


tmp=int(n*(n-1)/2)
ans=[0]*m
ans[-1]=tmp
#ans[0]=0
#print('a,b=',a,b)
for i in range(m-1,-1,-1):
    ans[i]=tmp
    if root(a[i])==root(b[i]):
        0
    else:
        tmp-=cnt_con[root(a[i])]*cnt_con[root(b[i])]
    connect(a[i],b[i])
    #print('i,tmp',i,(a[i],b[i]),ans[i],tmp,par,cnt_con)
    

    
for i in range(m):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
sys.setrecursionlimit(100000)

n, m=map(int, input().split())
a=[0 for i in range(m)]
b=[0 for i in range(m)]

par=[i for i in range(n)]
cnt_con=[1 for i in range(n)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
def connect(x,y):
    if root(x)==root(y):
        0
    else:
        cnt_con[root(y)]+=cnt_con[root(x)]
        par[root(x)]=root(y)      
    return

for i in range(m):
    a[i], b[i]=map(int, input().split())
    a[i], b[i]=a[i]-1, b[i]-1


tmp=int(n*(n-1)/2)
ans=[0]*m
ans[-1]=tmp
#ans[0]=0
#print('a,b=',a,b)
a=a[::-1]
b=b[::-1]
for i in range(m):
    ans[i]=tmp
    if root(a[i])==root(b[i]):
        0
    else:
        tmp-=cnt_con[root(a[i])]*cnt_con[root(b[i])]
    connect(a[i],b[i])
    #print('i,tmp',i,(a[i],b[i]),ans[i],tmp,par,cnt_con)
for i in range(m):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
n, m=map(int, input().split())
a=[0 for i in range(m)]
b=[0 for i in range(m)]

par=[i for i in range(n)]
cnt_con=[1 for i in range(n)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
def connect(x,y):
    if root(x)==root(y):
        0
    else:
        cnt_con[root(y)]+=cnt_con[root(x)]
        par[root(x)]=root(y)      
    return

for i in range(m):
    a[i], b[i]=map(int, input().split())
    a[i], b[i]=a[i]-1, b[i]-1


tmp=int(n*(n-1)/2)
ans=[0]*m
ans[-1]=tmp
#ans[0]=0
#print('a,b=',a,b)
a=a[::-1]
b=b[::-1]
for i in range(m):
    ans[i]=tmp
    if root(a[i])==root(b[i]):
        0
    else:
        tmp-=cnt_con[root(a[i])]*cnt_con[root(b[i])]
    connect(a[i],b[i])
    #print('i,tmp',i,(a[i],b[i]),ans[i],tmp,par,cnt_con)
for i in range(m):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
n, m=map(int, input().split())
a=[0 for i in range(m)]
b=[0 for i in range(m)]

par=[i for i in range(n)]
cnt_con=[1 for i in range(n)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
def connect(x,y):
    if root(x)==root(y):
        0
    else:
        cnt_con[root(y)]+=cnt_con[root(x)]
        par[root(x)]=root(y)      
    return

for i in range(m):
    a[i], b[i]=map(int, input().split())
    a[i], b[i]=a[i]-1, b[i]-1


tmp=int(n*(n-1)/2)
ans=[0]*m
ans[-1]=tmp
#ans[0]=0
#print('a,b=',a,b)
for i in range(m-1,-1,-1):
    ans[i]=tmp
    if root(a[i])==root(b[i]):
        0
    else:
        tmp-=cnt_con[root(a[i])]*cnt_con[root(b[i])]
    connect(a[i],b[i])
    #print('i,tmp',i,(a[i],b[i]),ans[i],tmp,par,cnt_con)
for i in range(m):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
n, m=map(int, input().split())
a=[0 for i in range(m)]
b=[0 for i in range(m)]
g=[list() for i in range(1+n)]
#print(g)

par=[i for i in range(n)]
cnt_con=[1 for i in range(n)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
def connect(x,y):
    #par[x]=root(x)
    #par[y]=root(y)
    if root(x)==root(y):
        0
    else:
        cnt_con[root(y)]+=cnt_con[root(x)]
        par[root(x)]=root(y)      
    return

for i in range(m):
    a[i], b[i]=map(int, input().split())
    a[i], b[i]=a[i]-1, b[i]-1


tmp=int(n*(n-1)/2)
ans=[0]*m
ans[-1]=tmp
#ans[0]=0
#print('a,b=',a,b)
for i in range(m-1,-1,-1):
    ans[i]=tmp
    if root(a[i])==root(b[i]):
        0
    else:
        tmp-=cnt_con[root(a[i])]*cnt_con[root(b[i])]
    connect(a[i],b[i])
    #print('i,tmp',i,(a[i],b[i]),ans[i],tmp,par,cnt_con)
    

    
for i in range(m):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
n, m=map(int, input().split())
a=[0 for i in range(m)]
b=[0 for i in range(m)]
g=[list() for i in range(1+n)]
#print(g)

par=[i for i in range(m)]
cnt_con=[1 for i in range(m)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
def connect(x,y):
    #par[x]=root(x)
    #par[y]=root(y)
    if root(x)==root(y):
        0
    else:
        cnt_con[root(y)]+=cnt_con[root(x)]
        par[root(x)]=root(y)      
    return

for i in range(m):
    a[i], b[i]=map(int, input().split())
    a[i], b[i]=a[i]-1, b[i]-1

tmp=int(n*(n-1)/2)
ans=[0]*m
ans[-1]=tmp
ans[0]=0
#print('a,b=',a,b)
for i in range(m-1,-1,-1):
    ans[i]=tmp
    if root(a[i])==root(b[i]):
        0
    else:
        tmp-=cnt_con[root(a[i])]*cnt_con[root(b[i])]
    connect(a[i],b[i])
    #print('i,tmp',i,(a[i],b[i]),ans[i],tmp,par,cnt_con)
    
        
    
for i in range(m):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
n, m=map(int, input().split())
a=[0 for i in range(m)]
b=[0 for i in range(m)]
g=[list() for i in range(1+n)]
#print(g)

root=[i for i in range(m)]
cnt_con=[1 for i in range(m)]

def parent(x):
    return root[x]
def connect(x,y):
    if root[x]==root[y]:
        0
    else:
        root[x]=root[y]
        cnt_con[root[y]]+=cnt_con[root[x]]
    return

for i in range(m):
    a[i], b[i]=map(int, input().split())
    a[i], b[i]=a[i]-1, b[i]-1

tmp=int(n*(n-1)/2)
ans=[0]*m
ans[-1]=tmp
ans[0]=0
#print('a,b=',a,b)
for i in range(m-1,-1,-1):
    ans[i]=tmp
    if root[a[i]]==root[b[i]]:
        0
    else:
        tmp-=cnt_con[a[i]]*cnt_con[b[i]]
    connect(a[i],b[i])
    #print('i,tmp',i,tmp,root,cnt_con)
        
    
for i in range(m):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
n, m=map(int, input().split())
a=[0 for i in range(m)]
b=[0 for i in range(m)]
g=[list() for i in range(1+n)]
#print(g)

root=[i for i in range(m)]
cnt_con=[1 for i in range(m)]

def parent(x):
    return root[x]
def connect(x,y):
    if root[x]==root[y]:
        0
    else:
        root[x]=root[y]
        cnt_con[root[y]]+=cnt_con[root[x]]
    return

for i in range(m):
    a[i], b[i]=map(int, input().split())
    a[i], b[i]=a[i]-1, b[i]-1

tmp=int(n*(n-1)/2)
ans=[0]*m
ans[-1]=tmp
ans[0]=0
#print('a,b=',a,b)
for i in range(m-1,0,-1):
    ans[i]=tmp
    if root[a[i]]==root[b[i]]:
        0
    else:
        tmp-=cnt_con[a[i]]*cnt_con[b[i]]
    connect(a[i],b[i])
    #print('i,tmp',i,tmp,root,cnt_con)
        
    
for i in range(m):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
n, m=map(int, input().split())
a=[0 for i in range(m)]
b=[0 for i in range(m)]
g=[list() for i in range(1+n)]
#print(g)

def Count_n_d(neighbor, start, search):
    visited = []
    stack = []
    stack.append(start)
    result = []
    while len(stack) > 0:
        next_city = stack.pop()
        if next_city in visited:
            continue
        result.append(next_city)
        visited.append(next_city)
        for nei in neighbor[next_city]:
            if nei==search:
                return [[]]                
            stack.append(nei)
    if search in result:
        return [[]]
    else:
        return [result]

def Count_n(neighbor, start, search):
    visited = []
    queue = []
    queue.append(start)
    result = []
    while len(queue) > 0:
        next_city = queue.pop(0)
        if next_city in visited:
            continue
        result.append (next_city)
        visited.append(next_city)
        for nei in neighbor[next_city]:
            queue.append(nei)
    if search in result:
        return [[]]
    else:
        return [result]
'''
print(g)
#print(Count(1,4,0))
for l in range(1,n+1):
    print('l,Count_n(g,l,0),len(Count_n(g,l,0))',l,Count_n(g,l,0),len(Count_n(g,l,0)[0]))
'''
for i in range(m):
    a[i], b[i]=map(int, input().split())
    g[a[i]].append(b[i])
    g[b[i]].append(a[i])
    #print(g)
tmp=int(m*(m-1)/2)
ans=[0]*m
for i in range(m,1,-1):
    
    cnt_a=len(Count_n(g,a[i],b[i])[0])
    if cnt_a==0:
        ans[i]=tmp
    else:
        tmp-=cnt_a*len(Count_n(g,b[i],0)[0])
        ans[i]=tmp
    
    g[a[i]].append(b[i])
    g[b[i]].append(a[i])
    
for i in range(m):
    print(ans[i])