Buggy python submission (verdict: Time Limit Exceeded):
import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def wantp(n): #Union-Find木の親の探索

    nown = n
    Q = []
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q: #探索した途中にあるノードの親を根に変更
                p[i] = nown
            break

    return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = [] #親
c = [] #子の数
rank = [1] * N #そのノードの子で構成された木の深さ

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M): #最後の橋から1本ずつ足していく

    a = AB[i][0]
    b = AB[i][1]

    ap = wantp(a)
    bp = wantp(b)


    now = ans[-1]

    if ap != bp: #前回の答えから導出、Union-Find木の結合
        now = now + nCr(c[ap],2) + nCr(c[bp],2) - nCr(c[ap]+c[bp],2)

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

        else:

            p[ap] = bp
            c[bp] += c[ap]

            rank[bp] += 1

    ans.append(now)

ans.reverse()

for i in range(M):
    print (ans[i+1])


Fixed submission:
import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def nC2(n):
    if n-2 >= 0:
        return (n*(n-1)) // 2
    else:
        return 0

def wantp(n): #Union-Find木の親の探索

    nown = n
    Q = []
    cnt = 0
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q: #探索した途中にあるノードの親を根に変更
                p[i] = nown
                cnt += 1

            break

        cnt += 1

        if cnt > 10:
            print (n,nown,p[nown])

    return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = [] #親
c = [] #子の数
rank = [1] * N #そのノードの子で構成された木の深さ

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M): #最後の橋から1本ずつ足していく

    #if i % 1000 == 0 or i > 25000:
        #print (i)

    #if i > 25000 : print ("A")

    a = AB[i][0]
    b = AB[i][1]

    #if i > 25000 : print ("B") 

    ap = wantp(a)
    bp = wantp(b)

    #if i > 25000 : print ("C")

    now = ans[-1]

    if ap != bp: #前回の答えから導出、Union-Find木の結合
        now = now + nC2(c[ap]) + nC2(c[bp]) - nC2(c[ap]+c[bp])

        #if i > 25000 : print ("D")

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

        else:

            p[ap] = bp
            c[bp] += c[ap]

            rank[bp] += 1

        #if i > 25000 : print ("E")

    ans.append(now)
    #if i > 25000 : print ("F")
    #print (now,p)

#print ("test")
ans.reverse()

for i in range(M):
    print (ans[i+1])

Buggy python submission (verdict: Time Limit Exceeded):
import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def wantp(n):

    nown = n
    Q = []
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            #for i in Q:
            #    p[i] = nown
            break

    return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = []
c = []
rank = [1] * N

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M):

    a = AB[i][0]
    b = AB[i][1]

    ap = wantp(a)
    bp = wantp(b)


    now = ans[-1]

    if ap != bp:
        now = now + nCr(c[ap],2) + nCr(c[bp],2) - nCr(c[ap]+c[bp],2)

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

        else:

            p[ap] = bp
            c[bp] += c[ap]

            rank[bp] += 1

    ans.append(now)

ans.reverse()

for i in range(M):
    print (ans[i+1])


Fixed submission:
import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def nC2(n):
    if n-2 >= 0:
        return (n*(n-1)) // 2
    else:
        return 0

def wantp(n): #Union-Find木の親の探索

    nown = n
    Q = []
    cnt = 0
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q: #探索した途中にあるノードの親を根に変更
                p[i] = nown
                cnt += 1

            break

        cnt += 1

        if cnt > 10:
            print (n,nown,p[nown])

    return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = [] #親
c = [] #子の数
rank = [1] * N #そのノードの子で構成された木の深さ

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M): #最後の橋から1本ずつ足していく

    #if i % 1000 == 0 or i > 25000:
        #print (i)

    #if i > 25000 : print ("A")

    a = AB[i][0]
    b = AB[i][1]

    #if i > 25000 : print ("B") 

    ap = wantp(a)
    bp = wantp(b)

    #if i > 25000 : print ("C")

    now = ans[-1]

    if ap != bp: #前回の答えから導出、Union-Find木の結合
        now = now + nC2(c[ap]) + nC2(c[bp]) - nC2(c[ap]+c[bp])

        #if i > 25000 : print ("D")

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

        else:

            p[ap] = bp
            c[bp] += c[ap]

            rank[bp] += 1

        #if i > 25000 : print ("E")

    ans.append(now)
    #if i > 25000 : print ("F")
    #print (now,p)

#print ("test")
ans.reverse()

for i in range(M):
    print (ans[i+1])

Buggy python submission (verdict: Time Limit Exceeded):
import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def wantp(n):

    nown = n
    Q = []
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q:
                p[i] = nown
            break

    return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = []
c = []
rank = [1] * N
#up2 = set([])

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M):

    a = AB[i][0]
    b = AB[i][1]

    ap = wantp(a)
    bp = wantp(b)


    now = ans[-1]

    if ap != bp:
        #print (now , nCr(rank[ap],2) , nCr(rank[bp],2) , nCr(rank[ap]+rank[bp],2))
        now = now + nCr(c[ap],2) + nCr(c[bp],2) - nCr(c[ap]+c[bp],2)

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

            #up2 = up2 - set([bp])
            #up2 = up2 | set([ap])

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

            #up2 = up2 - set([ap])
            #up2 = up2 | set([bp])

        else:

            p[ap] = bp
            c[bp] += c[ap]

            #up2 = up2 - set([ap])
            #up2 = up2 | set([bp])

            rank[bp] += 1

    #now = 0

    #for j in up2:

        #now += nCr(c[j],2)

    ans.append(now)

ans.reverse()

for i in range(M):
    print (ans[i+1])

Fixed submission:
import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def nC2(n):
    if n-2 >= 0:
        return (n*(n-1)) // 2
    else:
        return 0

def wantp(n): #Union-Find木の親の探索

    nown = n
    Q = []
    cnt = 0
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q: #探索した途中にあるノードの親を根に変更
                p[i] = nown
                cnt += 1

            break

        cnt += 1

        if cnt > 10:
            print (n,nown,p[nown])

    return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = [] #親
c = [] #子の数
rank = [1] * N #そのノードの子で構成された木の深さ

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M): #最後の橋から1本ずつ足していく

    #if i % 1000 == 0 or i > 25000:
        #print (i)

    #if i > 25000 : print ("A")

    a = AB[i][0]
    b = AB[i][1]

    #if i > 25000 : print ("B") 

    ap = wantp(a)
    bp = wantp(b)

    #if i > 25000 : print ("C")

    now = ans[-1]

    if ap != bp: #前回の答えから導出、Union-Find木の結合
        now = now + nC2(c[ap]) + nC2(c[bp]) - nC2(c[ap]+c[bp])

        #if i > 25000 : print ("D")

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

        else:

            p[ap] = bp
            c[bp] += c[ap]

            rank[bp] += 1

        #if i > 25000 : print ("E")

    ans.append(now)
    #if i > 25000 : print ("F")
    #print (now,p)

#print ("test")
ans.reverse()

for i in range(M):
    print (ans[i+1])

Buggy python submission (verdict: Time Limit Exceeded):
import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def wantp(n):

    nown = n
    Q = []
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q:
                p[i] = nown
            break

    return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = []
c = []
rank = [1] * N
up2 = set([])

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M):

    a = AB[i][0]
    b = AB[i][1]

    ap = wantp(a)
    bp = wantp(b)


    now = ans[-1]

    if ap != bp:
        #print (now , nCr(rank[ap],2) , nCr(rank[bp],2) , nCr(rank[ap]+rank[bp],2))
        now = now + nCr(c[ap],2) + nCr(c[bp],2) - nCr(c[ap]+c[bp],2)

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

            up2 = up2 - set([bp])
            up2 = up2 | set([ap])

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

            up2 = up2 - set([ap])
            up2 = up2 | set([bp])

        else:

            p[ap] = bp
            c[bp] += c[ap]

            up2 = up2 - set([ap])
            up2 = up2 | set([bp])

            rank[bp] += 1

    #now = 0

    #for j in up2:

        #now += nCr(c[j],2)

    ans.append(now)

ans.reverse()

for i in range(M):
    print (ans[i+1])


Fixed submission:
import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def nC2(n):
    if n-2 >= 0:
        return (n*(n-1)) // 2
    else:
        return 0

def wantp(n): #Union-Find木の親の探索

    nown = n
    Q = []
    cnt = 0
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q: #探索した途中にあるノードの親を根に変更
                p[i] = nown
                cnt += 1

            break

        cnt += 1

        if cnt > 10:
            print (n,nown,p[nown])

    return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = [] #親
c = [] #子の数
rank = [1] * N #そのノードの子で構成された木の深さ

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M): #最後の橋から1本ずつ足していく

    #if i % 1000 == 0 or i > 25000:
        #print (i)

    #if i > 25000 : print ("A")

    a = AB[i][0]
    b = AB[i][1]

    #if i > 25000 : print ("B") 

    ap = wantp(a)
    bp = wantp(b)

    #if i > 25000 : print ("C")

    now = ans[-1]

    if ap != bp: #前回の答えから導出、Union-Find木の結合
        now = now + nC2(c[ap]) + nC2(c[bp]) - nC2(c[ap]+c[bp])

        #if i > 25000 : print ("D")

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

        else:

            p[ap] = bp
            c[bp] += c[ap]

            rank[bp] += 1

        #if i > 25000 : print ("E")

    ans.append(now)
    #if i > 25000 : print ("F")
    #print (now,p)

#print ("test")
ans.reverse()

for i in range(M):
    print (ans[i+1])

Buggy python submission (verdict: Time Limit Exceeded):
import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def wantp(n):

    nown = n
    Q = []
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q:
                p[i] = nown
            break

    return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = []
c = []
rank = [1] * N
up2 = set([])

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M):

    a = AB[i][0]
    b = AB[i][1]

    ap = wantp(a)
    bp = wantp(b)


    now = ans[-1]

    if ap != bp:
        #print (now , nCr(rank[ap],2) , nCr(rank[bp],2) , nCr(rank[ap]+rank[bp],2))
        now = now + nCr(c[ap],2) + nCr(c[bp],2) - nCr(c[ap]+c[bp],2)

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

            up2 = up2 - set([bp])
            up2 = up2 | set([ap])

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

            up2 = up2 - set([ap])
            up2 = up2 | set([bp])

        else:

            p[ap] = bp
            c[bp] += c[ap]

            up2 = up2 - set([ap])
            up2 = up2 | set([bp])

            rank[bp] += 1

    #now = 0

    #for j in up2:

        #now += nCr(c[j],2)

    ans.append(now)

ans.reverse()

for i in range(M):
    print (ans[i+1])


Fixed submission:
import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def nC2(n):
    if n-2 >= 0:
        return (n*(n-1)) // 2
    else:
        return 0

def wantp(n): #Union-Find木の親の探索

    nown = n
    Q = []
    cnt = 0
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q: #探索した途中にあるノードの親を根に変更
                p[i] = nown
                cnt += 1

            break

        cnt += 1

        if cnt > 10:
            print (n,nown,p[nown])

    return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = [] #親
c = [] #子の数
rank = [1] * N #そのノードの子で構成された木の深さ

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M): #最後の橋から1本ずつ足していく

    #if i % 1000 == 0 or i > 25000:
        #print (i)

    #if i > 25000 : print ("A")

    a = AB[i][0]
    b = AB[i][1]

    #if i > 25000 : print ("B") 

    ap = wantp(a)
    bp = wantp(b)

    #if i > 25000 : print ("C")

    now = ans[-1]

    if ap != bp: #前回の答えから導出、Union-Find木の結合
        now = now + nC2(c[ap]) + nC2(c[bp]) - nC2(c[ap]+c[bp])

        #if i > 25000 : print ("D")

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

        else:

            p[ap] = bp
            c[bp] += c[ap]

            rank[bp] += 1

        #if i > 25000 : print ("E")

    ans.append(now)
    #if i > 25000 : print ("F")
    #print (now,p)

#print ("test")
ans.reverse()

for i in range(M):
    print (ans[i+1])

Buggy python submission (verdict: Time Limit Exceeded):
import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def wantp(n):

    nown = n
    Q = []
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q:
                p[i] = nown

            return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = []
c = []
rank = [1] * N
up2 = set([])

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M):

    a = AB[i][0]
    b = AB[i][1]

    ap = wantp(a)
    bp = wantp(b)


    now = ans[-1]

    if ap != bp:
        #print (now , nCr(rank[ap],2) , nCr(rank[bp],2) , nCr(rank[ap]+rank[bp],2))
        now = now + nCr(c[ap],2) + nCr(c[bp],2) - nCr(c[ap]+c[bp],2)

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

            up2 = up2 - set([bp])
            up2 = up2 | set([ap])

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

            up2 = up2 - set([ap])
            up2 = up2 | set([bp])

        else:

            p[ap] = bp
            c[bp] += c[ap]

            up2 = up2 - set([ap])
            up2 = up2 | set([bp])

            rank[bp] += 1

    #now = 0

    #for j in up2:

        #now += nCr(c[j],2)

    ans.append(now)

ans.reverse()

for i in range(M):
    print (ans[i+1])

Fixed submission:
import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def nC2(n):
    if n-2 >= 0:
        return (n*(n-1)) // 2
    else:
        return 0

def wantp(n): #Union-Find木の親の探索

    nown = n
    Q = []
    cnt = 0
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q: #探索した途中にあるノードの親を根に変更
                p[i] = nown
                cnt += 1

            break

        cnt += 1

        if cnt > 10:
            print (n,nown,p[nown])

    return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = [] #親
c = [] #子の数
rank = [1] * N #そのノードの子で構成された木の深さ

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M): #最後の橋から1本ずつ足していく

    #if i % 1000 == 0 or i > 25000:
        #print (i)

    #if i > 25000 : print ("A")

    a = AB[i][0]
    b = AB[i][1]

    #if i > 25000 : print ("B") 

    ap = wantp(a)
    bp = wantp(b)

    #if i > 25000 : print ("C")

    now = ans[-1]

    if ap != bp: #前回の答えから導出、Union-Find木の結合
        now = now + nC2(c[ap]) + nC2(c[bp]) - nC2(c[ap]+c[bp])

        #if i > 25000 : print ("D")

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

        else:

            p[ap] = bp
            c[bp] += c[ap]

            rank[bp] += 1

        #if i > 25000 : print ("E")

    ans.append(now)
    #if i > 25000 : print ("F")
    #print (now,p)

#print ("test")
ans.reverse()

for i in range(M):
    print (ans[i+1])

Buggy python submission (verdict: Time Limit Exceeded):
import math

def nCr(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

def wantp(n):

    nown = n
    Q = []
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q:
                p[i] = nown

            return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = []
c = []
rank = [1] * N
up2 = set([])

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M):

    a = AB[i][0]
    b = AB[i][1]

    ap = wantp(a)
    bp = wantp(b)

    if ap != bp:

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

            up2 = up2 - set([bp])
            up2 = up2 | set([ap])

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

            up2 = up2 - set([ap])
            up2 = up2 | set([bp])

        else:

            p[ap] = bp
            c[bp] += c[ap]

            up2 = up2 - set([ap])
            up2 = up2 | set([bp])

            rank[bp] += 1

    now = 0

    for j in up2:

        now += nCr(c[j],2)

    ans.append(nCr(N,2) - now)

ans.reverse()

for i in range(M):
    print (ans[i+1])


Fixed submission:
import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def nC2(n):
    if n-2 >= 0:
        return (n*(n-1)) // 2
    else:
        return 0

def wantp(n): #Union-Find木の親の探索

    nown = n
    Q = []
    cnt = 0
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q: #探索した途中にあるノードの親を根に変更
                p[i] = nown
                cnt += 1

            break

        cnt += 1

        if cnt > 10:
            print (n,nown,p[nown])

    return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = [] #親
c = [] #子の数
rank = [1] * N #そのノードの子で構成された木の深さ

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M): #最後の橋から1本ずつ足していく

    #if i % 1000 == 0 or i > 25000:
        #print (i)

    #if i > 25000 : print ("A")

    a = AB[i][0]
    b = AB[i][1]

    #if i > 25000 : print ("B") 

    ap = wantp(a)
    bp = wantp(b)

    #if i > 25000 : print ("C")

    now = ans[-1]

    if ap != bp: #前回の答えから導出、Union-Find木の結合
        now = now + nC2(c[ap]) + nC2(c[bp]) - nC2(c[ap]+c[bp])

        #if i > 25000 : print ("D")

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

        else:

            p[ap] = bp
            c[bp] += c[ap]

            rank[bp] += 1

        #if i > 25000 : print ("E")

    ans.append(now)
    #if i > 25000 : print ("F")
    #print (now,p)

#print ("test")
ans.reverse()

for i in range(M):
    print (ans[i+1])

Buggy python submission (verdict: Time Limit Exceeded):
import math

def nCr(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

def wantp(n):

    nown = n
    Q = []
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q:
                p[i] = nown

            return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = []
c = []
rank = [1] * N
up2 = set([])

for i in range(N):

    p.append(i)
    c.append(set([i]))

for i in range(M):

    a = AB[i][0]
    b = AB[i][1]

    ap = wantp(a)
    bp = wantp(b)

    if ap != bp:

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] = c[ap] | c[bp]

            up2 = up2 - set([bp])
            up2 = up2 | set([ap])

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] = c[ap] | c[bp]

            up2 = up2 - set([ap])
            up2 = up2 | set([bp])

        else:

            p[ap] = bp
            c[bp] = c[ap] | c[bp]

            up2 = up2 - set([ap])
            up2 = up2 | set([bp])

            rank[bp] += 1

    now = 0

    for j in up2:

        now += nCr(len(c[j]),2)

    ans.append(nCr(N,2) - now)

ans.reverse()

for i in range(M):
    print (ans[i+1])


Fixed submission:
import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def nC2(n):
    if n-2 >= 0:
        return (n*(n-1)) // 2
    else:
        return 0

def wantp(n): #Union-Find木の親の探索

    nown = n
    Q = []
    cnt = 0
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q: #探索した途中にあるノードの親を根に変更
                p[i] = nown
                cnt += 1

            break

        cnt += 1

        if cnt > 10:
            print (n,nown,p[nown])

    return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = [] #親
c = [] #子の数
rank = [1] * N #そのノードの子で構成された木の深さ

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M): #最後の橋から1本ずつ足していく

    #if i % 1000 == 0 or i > 25000:
        #print (i)

    #if i > 25000 : print ("A")

    a = AB[i][0]
    b = AB[i][1]

    #if i > 25000 : print ("B") 

    ap = wantp(a)
    bp = wantp(b)

    #if i > 25000 : print ("C")

    now = ans[-1]

    if ap != bp: #前回の答えから導出、Union-Find木の結合
        now = now + nC2(c[ap]) + nC2(c[bp]) - nC2(c[ap]+c[bp])

        #if i > 25000 : print ("D")

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

        else:

            p[ap] = bp
            c[bp] += c[ap]

            rank[bp] += 1

        #if i > 25000 : print ("E")

    ans.append(now)
    #if i > 25000 : print ("F")
    #print (now,p)

#print ("test")
ans.reverse()

for i in range(M):
    print (ans[i+1])

Buggy python submission (verdict: Time Limit Exceeded):
import math

def nCr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))



N,M = map(int,input().split())

AB = []
ans = []
p = []
c = []
nums = [1] * N

up2 = set([])

for i in range(M):

    A,B = map(int,input().split())
    AB.append([A-1,B-1])

for i in range(N):
    p.append(i)
    c.append(set([i]))
    

AB.reverse()

ans.append(nCr(N,2))

for i in range(M):

    #print (p,c,up2)
    #print (nums)

    if p[AB[i][0]] != p[AB[i][1]] and nums[p[AB[i][0]]] >= nums[p[AB[i][1]]]: # 1を0に統合

        #p[AB[i][1]] = AB[i][0]

        #up2 = up2 | set([AB[i][0]])


        nums[p[AB[i][0]]] += nums[p[AB[i][1]]]
        c[p[AB[i][0]]] = c[p[AB[i][0]]] | c[p[AB[i][1]]]

        up2 = up2 - set([p[AB[i][1]]])
        up2 = up2 | set([p[AB[i][0]]])

        for j in c[p[AB[i][1]]]:

            p[j] = p[AB[i][0]]

        

    elif p[AB[i][0]] != p[AB[i][1]]:

        nums[p[AB[i][1]]] += nums[p[AB[i][0]]]
        c[p[AB[i][1]]] = c[p[AB[i][1]]] | c[p[AB[i][0]]]

        up2 = up2 - set([p[AB[i][0]]])
        up2 = up2 | set([p[AB[i][1]]])

        for j in c[p[AB[i][0]]]:

            p[j] = p[AB[i][1]]

    now = 0


    
    for j in up2:

        now += nCr(nums[j],2)

    ans.append(nCr(N,2)-now)

ans.reverse()

for i in range(M):
    print (ans[i+1])


Fixed submission:
import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def nC2(n):
    if n-2 >= 0:
        return (n*(n-1)) // 2
    else:
        return 0

def wantp(n): #Union-Find木の親の探索

    nown = n
    Q = []
    cnt = 0
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q: #探索した途中にあるノードの親を根に変更
                p[i] = nown
                cnt += 1

            break

        cnt += 1

        if cnt > 10:
            print (n,nown,p[nown])

    return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = [] #親
c = [] #子の数
rank = [1] * N #そのノードの子で構成された木の深さ

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M): #最後の橋から1本ずつ足していく

    #if i % 1000 == 0 or i > 25000:
        #print (i)

    #if i > 25000 : print ("A")

    a = AB[i][0]
    b = AB[i][1]

    #if i > 25000 : print ("B") 

    ap = wantp(a)
    bp = wantp(b)

    #if i > 25000 : print ("C")

    now = ans[-1]

    if ap != bp: #前回の答えから導出、Union-Find木の結合
        now = now + nC2(c[ap]) + nC2(c[bp]) - nC2(c[ap]+c[bp])

        #if i > 25000 : print ("D")

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

        else:

            p[ap] = bp
            c[bp] += c[ap]

            rank[bp] += 1

        #if i > 25000 : print ("E")

    ans.append(now)
    #if i > 25000 : print ("F")
    #print (now,p)

#print ("test")
ans.reverse()

for i in range(M):
    print (ans[i+1])