Buggy python submission (verdict: Time Limit Exceeded):
(n,m) = map(int,input().split())
a,A,b,me,d,w,s = [0]*m,[0]*m,[-1]*n,[1]*n,[0]*n,[0]*m,(n*(n-1))//2
for i in range(m):
    (a[i], A[i]) = map(int,input().split())
    a[i] -= 1
    A[i] -= 1
w[m-1] = s
 
def se(i, b):
     m = 0
     while b[i] >= 0:
          i = b[i]
          m += 1
     return i,m
 
for j in range(m-1):
     i = m-j-1
     i1,i2 = a[i],A[i]
     p1,m1 = se(i1, b)
     p2,m2 = se(i2, b)
     if p1 != p2:
          if d[m1] < d[m2]:
               (p1,p2) = (p2,p1)
          b[p2] = p1
          s -= me[p1]*me[p2]
          me[p1] += me[p2]
          me[p2] = 0
          d[p1] = max(d[p1],d[p2]+1)
     w[i-1] = s
         
for i in range(m):
     print(w[i])

Fixed submission:
#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
(n,m) = map(int,input().split())
a,A,b,me,d,w,s = [0]*m,[0]*m,[-1]*n,[1]*n,[0]*n,[0]*m,(n*(n-1))//2
for i in range(m):
    (a[i], A[i]) = map(int,input().split())
    a[i] -= 1
    A[i] -= 1
w[m-1] = s
 
def se(i, b):
     m = 0
     while b[i] >= 0:
          i = b[i]
          m += 1
     return i,m
 
for j in range(m-1):
     i = m-j-1
     i1,i2 = a[i],A[i]
     p1,m1 = se(i1, b)
     p2,m2 = se(i2, b)
     if p1 != p2:
          if d[m1] < d[m2]:
               (p1,p2) = (p2,p1)
          b[p2] = p1
          s -= me[p1]*me[p2]
          me[p1] += me[p2]
          me[p2] = 0
          d[p1] = max(d[p1],d[p2]+1)
     w[i-1] = s
         
for i in range(m):
     print(w[i])

Fixed submission:
#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
(n,m) = map(int,input().split())
a,A,b,me,d,w,s = [0]*m,[0]*m,[-1]*n,[1]*n,[0]*n,[0]*m,(n*(n-1))//2
for i in range(m):
    (a[i], A[i]) = map(int,input().split())
    a[i] -= 1
    A[i] -= 1
w[m-1] = s
 
def se(i, b):
     m = 0
     while b[i] >= 0:
          i = b[i]
          m += 1
     return i,m
 
for j in range(m-1):
     i = m-j-1
     i1,i2 = a[i],A[i]
     p1,m1 = se(i1, b)
     p2,m2 = se(i2, b)
     if p1 != p2:
          if d[m1] < d[m2]:
               (p1,p2) = (p2,p1)
          b[p2] = p1
          s -= me[p1]*me[p2]
          me[p1] += me[p2]
          me[p2] = 0
          d[p1] = max(d[p1],d[p2]+1)
     w[i-1] = s
         
for i in range(m):
     print(w[i])

Fixed submission:
#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
(n,m) = map(int,input().split())
a,A,b,me,d,w,s = [0]*m,[0]*m,[-1]*n,[1]*n,[0]*n,[0]*m,(n*(n-1))//2
for i in range(m):
    (a[i], A[i]) = map(int,input().split())
    a[i] -= 1
    A[i] -= 1
w[m-1] = s
 
def se(i, b):
     m = 0
     while b[i] >= 0:
          i = b[i]
          m += 1
     return i,m
 
for j in range(m-1):
     i = m-j-1
     i1,i2 = a[i],A[i]
     p1,m1 = se(i1, b)
     p2,m2 = se(i2, b)
     if p1 != p2:
          if d[m1] < d[m2]:
               (p1,p2) = (p2,p1)
          b[p2] = p1
          s -= me[p1]*me[p2]
          me[p1] += me[p2]
          me[p2] = 0
          d[p1] = max(d[p1],d[p2]+1)
     w[i-1] = s
         
for i in range(m):
     print(w[i])

Fixed submission:
#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
(n,m) = map(int,input().split())
a,A = [0]*m,[0]*m
for i in range(m):
    (a[i], A[i]) = map(int,input().split())
    a[i] -= 1
    A[i] -= 1
b = [-1]*n
me = [1]*n
d = [0]*n
w = [0]*m
s = (n*(n-1))//2
w[m-1] = s
 
def se(i, b):
     m = 0
     while b[i] >= 0:
          i = b[i]
          m += 1
     return i,m
 
for j in range(m-1):
     i = m-j-1
     i1,i2 = a[i],A[i]
     p1,m1 = se(i1, b)
     p2,m2 = se(i2, b)
     if p1 != p2:
          if d[m1] < d[m2]:
               (p1,p2) = (p2,p1)
          b[p2] = p1
          s -= me[p1]*me[p2]
          me[p1] += me[p2]
          me[p2] = 0
          d[p1] = max(d[p1],d[p2]+1)
     w[i-1] = s
         
for i in range(m):
     print(w[i])

Fixed submission:
#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
a,A = [0]*m,[0]*m
for i in range(m):
    (a[i], A[i]) = map(int,input().split())
    a[i] -= 1
    A[i] -= 1
b = [-1]*n
me = [1]*n
d = [0]*n
w = [0]*m
s = (n*(n-1))//2
w[m-1] = s
 
def se(i, b):
     m = 0
     while b[i] >= 0:
          i = b[i]
          m += 1
     return i,m
 
for j in range(m-1):
     i = m-j-1
     i1,i2 = a[i],A[i]
     p1,m1 = se(i1, b)
     p2,m2 = se(i2, b)
     if p1 != p2:
          if d[m1] < d[m2]:
               (p1,p2) = (p2,p1)
          b[p2] = p1
          s -= me[p1]*me[p2]
          me[p1] += me[p2]
          me[p2] = 0
          d[p1] = max(d[p1],d[p2]+1)
     w[i-1] = s
         
for i in range(m):
     print(w[i])

Fixed submission:
#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
isl1 = [0]*m
isl2 = [0]*m
for i in range(m):
    (isl1[i], isl2[i]) = map(int,input().split())
    isl1[i] -= 1
    isl2[i] -= 1
boss = [-1]*n
mem = [1]*n
dpt = [0]*n
ans = [0]*m
s = (n*(n-1))//2
ans[m-1] = s
 
def sea(i, boss):
     m = 0
     while boss[i] >= 0:
          i = boss[i]
          m += 1
     return i,m
 
for j in range(m-1):
     i = m-j-1
     i1,i2 = isl1[i],isl2[i]
     p1,m1 = sea(i1, boss)
     p2,m2 = sea(i2, boss)
     if p1 != p2:
          if dpt[m1] < dpt[m2]:
               (p1,p2) = (p2,p1)
          boss[p2] = p1
          s -= mem[p1]*mem[p2]
          mem[p1] += mem[p2]
          mem[p2] = 0
          dpt[p1] = max(dpt[p1],dpt[p2]+1)
     ans[i-1] = s
         
for i in range(m):
     print(ans[i])

Fixed submission:
#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
isl1,isl2 = [0]*m,[0]*m
for i in range(m):
    (isl1[i], isl2[i]) = map(int,input().split())
    isl1[i] -= 1
    isl2[i] -= 1
boss = [-1]*n
mem = [1]*n
dpt = [0]*n
ans = [0]*m
s = (n*(n-1))//2
ans[m-1] = s
 
def sea(island, boss):
     m = 0
     while boss[island] >= 0:
          island = boss[island]
          m += 1
     return island,m
 
for j in range(m-1):
     i = m-j-1
     i1,i2 = isl1[i],isl2[i]
     p1,m1 = sea(i1, boss)
     p2,m2 = sea(i2, boss)
     if p1 != p2:
          if dpt[m1] < dpt[m2]:
               (p1,p2) = (p2,p1)
          boss[p2] = p1
          s -= mem[p1]*mem[p2]
          mem[p1] += mem[p2]
          mem[p2] = 0
          dpt[p1] = max(dpt[p1],dpt[p2]+1)
     ans[i-1] = s
         
for i in range(m):
     print(ans[i])

Fixed submission:
#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
isl1,isl2 = [0]*m,[0]*m
for i in range(m):
    (isl1[i], isl2[i]) = map(int,input().split())
    isl1[i] -= 1
    isl2[i] -= 1
boss = [-1]*n
member_number = [1]*n
dpt = [0]*n

ans = [0]*m
s = (n*(n-1))//2
ans[m-1] = s
 
def search_member(island, boss):
     m = 0
     while boss[island] >= 0:
          island = boss[island]
          m += 1
     return island,m
 
for j in range(m-1):
     i = m-j-1
     island1,island2 = isl1[i],isl2[i]
     parent1,m1 = search_member(island1, boss)
     parent2,m2 = search_member(island2, boss)
     if parent1 != parent2:
          if dpt[m1] < dpt[m2]:
               (parent1,parent2) = (parent2,parent1)
          boss[parent2] = parent1
          s -= member_number[parent1]*member_number[parent2]
          member_number[parent1] += member_number[parent2]
          member_number[parent2] = 0
          dpt[parent1] = max(dpt[parent1],dpt[parent2]+1)
     ans[i-1] = s
         
for i in range(m):
     print(ans[i])

Fixed submission:
#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
br = [list(map(int,input().split())) for i in range(m)]
boss = [-1]*n
member_number = [1]*n
dpt = [0]*n

ans = [0]*m
s = (n*(n-1))//2
ans[m-1] = s
 
def search_member(island, boss):
     m = 0
     while boss[island] >= 0:
          island = boss[island]
          m += 1
     return island,m
 
for j in range(m-1):
     i = m-j-1
     island1,island2 = br[i][0]-1,br[i][1]-1
     parent1,m1 = search_member(island1, boss)
     parent2,m2 = search_member(island2, boss)
     if parent1 != parent2:
          if dpt[m1] < dpt[m2]:
               (parent1,parent2) = (parent2,parent1)
          boss[parent2] = parent1
          s -= member_number[parent1]*member_number[parent2]
          member_number[parent1] += member_number[parent2]
          member_number[parent2] = 0
          dpt[parent1] = max(dpt[parent1],dpt[parent2]+1)
     ans[i-1] = s
         
for i in range(m):
     print(ans[i])

Fixed submission:
#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
br = [list(map(int,input().split())) for i in range(m)]
boss = [-1]*n
member_number = [1]*n
dpt = [0]*n

ans = [0]*m
s = (n*(n-1))//2
ans[m-1] = s
 
def search_member(island, boss):
     m = 0
     while boss[island] >= 0:
          island = boss[island]
          m += 1
     return island,m
 
for i in range(m-1,0,-1):
     island1,island2 = br[i][0]-1,br[i][1]-1
     parent1,m1 = search_member(island1, boss)
     parent2,m2 = search_member(island2, boss)
     if parent1 != parent2:
          if dpt[m1] < dpt[m2]:
               (parent1,parent2) = (parent2,parent1)
          boss[parent2] = parent1
          s -= member_number[parent1]*member_number[parent2]
          member_number[parent1] += member_number[parent2]
          member_number[parent2] = 0
          dpt[parent1] = max(dpt[parent1],dpt[parent2]+1)
     ans[i-1] = s
         
for i in range(m):
     print(ans[i])

Fixed submission:
#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
br = [list(map(int,input().split())) for i in range(m)]
ans = [(n*(n-1))//2]
boss = [-1]*n
member_number = [1]*n
dpt = [0]*n
 
def search_member(island, boss):
     m = 0
     while boss[island] >= 0:
          island = boss[island]
          m += 1
     return island,m
 
for i in range(m-1,-1,-1):
     island1,island2 = br[i][0]-1,br[i][1]-1
     parent1,m1 = search_member(island1, boss)
     parent2,m2 = search_member(island2, boss)
     if parent1 != parent2:
          if dpt[m1] < dpt[m2]:
               (parent1,parent2) = (parent2,parent1)
          boss[parent2] = parent1
          ans.append(ans[-1] - member_number[parent1]*member_number[parent2])
          member_number[parent1] += member_number[parent2]
          member_number[parent2] = 0
          dpt[parent1] = max(dpt[parent1],dpt[parent2]+1)
     else:
          ans.append(ans[-1])
         
for i in range(m-1,-1,-1):
     print(ans[i])

Fixed submission:
#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
br = [list(map(int,input().split())) for i in range(m)]
ans = [(n*(n-1))//2]
boss = [-1]*n
member_number = [1]*n
 
def search_member(island, boss):
     while boss[island] >= 0:
          island = boss[island]
     return island
 
for i in range(m-1,-1,-1):
     island1,island2 = br[i][0]-1,br[i][1]-1
     parent1 = search_member(island1, boss)
     parent2 = search_member(island2, boss)
     if parent1 != parent2:
          boss[parent2] = parent1
          ans.append(ans[-1] - member_number[parent1]*member_number[parent2])
          member_number[parent1] += member_number[parent2]
          member_number[parent2] = 0
     else:
          ans.append(ans[-1])
         
for i in range(m-1,-1,-1):
     print(ans[i])

Fixed submission:
#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
br = [list(map(int,input().split())) for i in range(m)]
ans = [(n*(n-1))//2]
member = [[i] for i in range(n)]

def search_member(br_i, member):
     flag = 0
     br_mem_num =[]
     mem_1 = br_i[0] - 1
     mem_2 = br_i[1] - 1
     for i in range(len(member)):
          if mem_1 in member[i]:
               br_mem_num.append(i)
               flag += 1
          if mem_2 in member[i]:
               br_mem_num.append(i)
               flag += 1
          if flag == 2:
               break
     return br_mem_num
     
def change_member(br_mem_num, member):
     mem1_num = br_mem_num[0]
     mem2_num = br_mem_num[1]
     member[mem1_num] += member[mem2_num]
     member[mem1_num].sort()
     member[mem2_num] = []

for i in range(m-1,-1,-1):
     br_i = br[i]
     br_mem_num = search_member(br_i, member)
     if br_mem_num[0] != br_mem_num[1]:
          len_1, len_2 = len(member[br_mem_num[0]]), len(member[br_mem_num[1]])
          ans.append(ans[-1] - (len_1*len_2))
          change_member(br_mem_num, member)
     else:
          ans.append(ans[-1])

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

Fixed submission:
#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
br = [list(map(int,input().split())) for i in range(m)]
ans = [(n*(n-1))//2]
member = [[i] for i in range(n)]

def search_member(br_i, member):
     flag = 0
     br_mem_num =[]
     mem_1 = br_i[0] - 1
     mem_2 = br_i[1] - 1
     for i in range(len(member)):
          if mem_1 in member[i]:
               br_mem_num.append(i)
               flag += 1
          if mem_2 in member[i]:
               br_mem_num.append(i)
               flag += 1
          if flag == 2:
               break
     return br_mem_num
     
def change_member(br_mem_num, member):
     mem1_num = br_mem_num[0]
     mem2_num = br_mem_num[1]
     member[mem1_num] += member[mem2_num]
     member[mem2_num] = []

for i in range(m-1,-1,-1):
     br_i = br[i]
     br_mem_num = search_member(br_i, member)
     if br_mem_num[0] != br_mem_num[1]:
          len_1, len_2 = len(member[br_mem_num[0]]), len(member[br_mem_num[1]])
          ans.append(ans[-1] - (len_1*len_2))
          change_member(br_mem_num, member)
     else:
          ans.append(ans[-1])

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

Fixed submission:
#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])