Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
X, Y, A, B, C = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
q = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
p.sort()
q.sort()
r.sort(reverse=True)
p = p[A - X:]
q = q[B - Y:]
pi = 0
qi = 0
for v in r:
    if p[pi] < v or q[qi] < v:
        if p[pi] < q[qi]:
            p[pi] = v
            pi = min(pi + 1, A - 1)
        else:
            q[qi] = v
            qi = min(qi + 1, B - 1)
    else:
        break
print(sum(p) + sum(q))

Fixed submission:
X, Y, A, B, C = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
q = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
p.sort()
q.sort()
r.sort(reverse=True)
p = p[A - X:]
q = q[B - Y:]
pi = 0
qi = 0
for v in r:
    if p[pi] < v or q[qi] < v:
        if p[pi] < q[qi]:
            p[pi] = v
            pi = min(pi + 1, X - 1)
        else:
            q[qi] = v
            qi = min(qi + 1, Y - 1)
    else:
        break
print(sum(p) + sum(q))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from math import ceil
H, W = [int(i) for i in input().split()]
s = [input() for _ in range(H)]

dq = deque()
D = [[999999999999]*W for _ in range(H)]
if s[0][0] == '.':
    D[0][0] = 0
else:
    D[0][0] = 1
dq.append((1, 0, s[0][0], D[0][0]))
dq.append((0, 1, s[0][0], D[0][0]))

while len(dq):
    h, w, m, d = dq.popleft()
    if s[h][w] != m:
        d += 1
    D[h][w] = min(D[h][w], d)

    for nh, nw in ((h+1, w), (h, w+1)):
        if nh < H and nw < W:
            dq.append((nh, nw, s[h][w], d))
print(ceil(D[-1][-1]/2))


Fixed submission:
from collections import deque
from math import ceil
H, W = [int(i) for i in input().split()]
s = [input() for _ in range(H)]

dq = deque()
D = [[999999999999]*W for _ in range(H)]
if s[0][0] == '.':
    D[0][0] = 0
else:
    D[0][0] = 1
dq.append((0, 0, s[0][0]))

while len(dq):
    h, w, m = dq.popleft()
    d = D[h][w]

    for nh, nw in ((h+1, w), (h, w+1)):
        if nh < H and nw < W:
            if D[nh][nw] == 999999999999:
                dq.append((nh, nw, s[nh][nw]))
            if s[nh][nw] != m:
                D[nh][nw] = min(D[nh][nw], d+1)
            else:
                D[nh][nw] = min(D[nh][nw], d)

print(ceil(D[-1][-1]/2))
Buggy python submission (verdict: Time Limit Exceeded):
S=input()
Q=int(input())
query=[[i for i in input().split()] for _ in range(Q)]

rf=0
for q in query:
    if q[0] == "1":
        rf ^= 1
    else:
        if q[1] == '1':
            if rf:
                # S = S + q[2]
                S = ''.join([S, q[2]])
            else:
                # S = q[2] + S
                S = ''.join([q[2], S])
        else:
            if rf:
                S = ''.join([q[2], S])
            else: 
                S = ''.join([S, q[2]])
print(S[::-1] if rf else S)

Fixed submission:
from collections import deque
S = deque([input()])
Q=int(input())
query=[[i for i in input().split()] for _ in range(Q)]

rf=0
for q in query:
    if q[0] == "1":
        rf ^= 1
    else:
        if q[1] == '1':
            if rf:
                S.append(q[2])
            else:
                S.appendleft(q[2])
        else:
            if rf:
                S.appendleft(q[2])
            else: 
                S.append(q[2])
print(''.join(S)[::-1] if rf else ''.join(S))

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
Q=int(input())
query=[[i for i in input().split()] for _ in range(Q)]

rf=0
for q in query:
    if q[0] == "1":
        rf ^= 1
    else:
        if q[1] == '1':
            if rf:
                S = S + q[2]
            else:
                S = q[2] + S
        else:
            if rf:
                S = q[2] + S
            else: 
                S = S + q[2]
print(S[::-1] if rf else S)

Fixed submission:
from collections import deque
S = deque([input()])
Q=int(input())
query=[[i for i in input().split()] for _ in range(Q)]

rf=0
for q in query:
    if q[0] == "1":
        rf ^= 1
    else:
        if q[1] == '1':
            if rf:
                S.append(q[2])
            else:
                S.appendleft(q[2])
        else:
            if rf:
                S.appendleft(q[2])
            else: 
                S.append(q[2])
print(''.join(S)[::-1] if rf else ''.join(S))
Buggy python submission (verdict: Runtime Error):
	mod = 10**9+7
N, A, B = [int(i) for i in input().split()]


def ncr(n, r):
    r = min(r, n-r)
    res = 1
    m = n
    for _ in range(r):
        res *= m
        res %= mod
        m -= 1
    m = r
    for _ in range(r):
        res *= pow(m, mod-2, mod)
        res %= mod
        m -= 1
    return res


print((pow(2, N, mod)-1-ncr(N, A)-ncr(N, B)) % mod)


Fixed submission:
mod = 10**9+7
N, A, B = [int(i) for i in input().split()]


def ncr(n, r):
    r = min(r, n-r)
    res = 1
    m = n
    for _ in range(r):
        res *= m
        res %= mod
        m -= 1
    m = r
    for _ in range(r):
        res *= pow(m, mod-2, mod)
        res %= mod
        m -= 1
    return res


print((pow(2, N, mod)-1-ncr(N, A)-ncr(N, B)) % mod)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
mod = 10**9+7
A.sort()
ans = 0
m = K
d = 1
n = 1
for i in range(K-1, N):
    ans += A[i]*n
    ans -= A[-i-1]*n
    n = n*m//d
    m += 1
    d += 1
    ans %= mod
print(ans)


Fixed submission:
mod = 10**9+7
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
A.sort()
ans = 0
m = K
d = 1
n = 1
for i in range(K-1, N):
    ans += A[i]*n
    ans -= A[-i-1]*n
    n *= pow(d, mod-2, mod)
    n = n*m % mod
    m += 1
    d += 1
    ans %= mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import queue
N = int(input())
br = []
alist = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    br.append([a, b])
    alist[a].append(b)
    alist[b].append(a)

q = queue.Queue()
ans = dict()
typeNum = 0
for a in alist:
    typeNum = max(typeNum, len(a))

f = [False]*(N+1)
q.put([1, 1])
f[1] = True
while not q.empty():
    n = q.get()
    c = n[1]
    for nxt in alist[n[0]]:
        if not f[nxt]:
            ans[str(sorted([n[0], nxt]))] = c
            c = c % typeNum+1
            q.put([nxt, c])
            f[nxt] = True

print(typeNum)
for k in br:
    print(ans[str(k)])


Fixed submission:
import sys
import queue
input = sys.stdin.readline

N = int(input())
alist = [[] for _ in range(N+1)]
idx = {}
for i in range(N-1):
    a, b = map(int, input().split())
    alist[a].append(b)
    alist[b].append(a)
    idx[(a, b)] = i
    idx[(b, a)] = i

q = queue.Queue()
ans = [0]*(N-1)
typeNum = 0
for a in alist:
    typeNum = max(typeNum, len(a))

f = [False]*(N+1)
q.put([1, 1])
f[1] = True
while not q.empty():
    n = q.get()
    c = n[1]
    for nxt in alist[n[0]]:
        if not f[nxt]:
            ans[idx[(n[0], nxt)]] = c
            c = c % typeNum+1
            q.put([nxt, c])
            f[nxt] = True

print(typeNum)
print(*ans, sep='\n')
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
# -*- Coding: utf-8 -*-

import sys


def main():
    S = input()
    K = int(input())
    ary = []
    ans = 0
    n = 1

    for i, s in enumerate(S[1:]):
        if s == S[i]:
            n += 1
        else:
            ary.append(n)
            n = 1
    if n != 1:
        ary.append(n)

    if S[0] == S[-1]:
        for num in ary[1:-1]:
            ans += num//2
        ans *= K
        if len(ary) == 1:
            ans += ary[0]*K//2
        else:
            ans += (ary[0]+ary[-1])//2*(K-1)
            ans += ary[0]//2+ary[-1]//2
    else:
        for num in ary:
            ans += num//2
        ans *= K
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
# -*- Coding: utf-8 -*-

import sys


def main():
    S = input()
    K = int(input())
    ary = []
    ans = 0
    n = 1

    for i, s in enumerate(S[1:]):
        if s == S[i]:
            n += 1
        else:
            ary.append(n)
            n = 1
    if n != 1:
        ary.append(n)

    if S[0] == S[-1]:
        for num in ary[1:-1]:
            ans += num//2
        ans *= K
        if len(ary) == 1:
            ans += ary[0]*K//2
        elif len(ary) < 1:
            ans = K//2
        else:
            ans += (ary[0]+ary[-1])//2*(K-1)
            ans += ary[0]//2+ary[-1]//2
    else:
        for num in ary:
            ans += num//2
        ans *= K
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys


def input():
    return sys.stdin.readline()[:-1]


def main():
    N = int(input())
    B = [int(i) for i in input().split()]
    b = B.copy()
    for i in (range(N-3, -1, -1)):
        if B[i] > B[i+1]:
            B[i] = B[i+1]

    for i in range(N-2):
        if b[i] < b[i+1]:
            b[i+1] = b[i]
    ans1 = sum(B)+B[0]
    ans2 = sum(b)+b[len(b)-1]
    print(ans1 if ans1 >= ans2 else ans2)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    N = int(input())
    B = [int(i) for i in input().split()]

    A = [B[0]]
    for i in range(1, len(B)):
        A.append(min([B[i], B[i-1]]))

    A.append(B[-1])
    print(sum(A))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys


def input():
    return sys.stdin.readline()[:-1]


def main():
    n = int(input())
    s = [sorted(list(input())) for _ in range(n)]
    ans = 0

    for i in range(n):
        for k in range(i+1, n):
            if s[i] == s[k]:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
import sys
import collections


def input():
    return sys.stdin.readline()[:-1]


def main():
    n = int(input())
    s = ["".join(sorted(list(input()))) for _ in range(n)]
    c = collections.Counter(s)
    ans = 0
    for k in c.values():
        ans += k*(k-1)//2

    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys


def main():
    S = input()

    MOD = 10**9+7
    dp = [[0]*13 for _ in range(len(S)+1)]
    dp[0][0] = 1

    for i in range(len(S)):
        if S[i] == "?":
            c = -1
        else:
            c = int(S[i])
        for j in range(10):
            if c != -1 and c != j:
                continue
            for ki in range(13):
                dp[i+1][(ki*10+j) % 13] += dp[i][ki]

    print(dp[len(S)][5] % MOD)


if __name__ == "__main__":
    main()


Fixed submission:
S = input()
mod = 10**9+7
dp = [[0]*13 for _ in range(len(S)+1)]
d = 1
dp[0][0] = 1

for i, s in enumerate(S[::-1]):
    if s == "?":
        for j in range(13):
            for k in range(10):
                dp[i+1][(j+(d*k)) % 13] += dp[i][j]
    else:
        for j in range(13):
            dp[i+1][(j+(d*int(s))) % 13] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= mod
    d = (d*10) % 13
print(dp[-1][5])

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = input()[::-1]

    MOD = 10**9+7
    dp = [[0]*13 for _ in range(len(S)+1)]
    dp[0][0] = 1

    for i in range(1, len(S)+1):
        if S[i-1] == "?":
            N = [(u*10**(i-1)) % 13 for u in range(10)]
        else:
            N = [(int(S[i-1])*10**(i-1)) % 13]
        for n in N:
            for j in range(13):
                dp[i][j] += dp[i-1][j-n % 13]

    print(dp[len(S)][5] % MOD)


if __name__ == "__main__":
    main()


Fixed submission:
S = input()
mod = 10**9+7
dp = [[0]*13 for _ in range(len(S)+1)]
d = 1
dp[0][0] = 1

for i, s in enumerate(S[::-1]):
    if s == "?":
        for j in range(13):
            for k in range(10):
                dp[i+1][(j+(d*k)) % 13] += dp[i][j]
    else:
        for j in range(13):
            dp[i+1][(j+(d*int(s))) % 13] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= mod
    d = (d*10) % 13
print(dp[-1][5])
Buggy python submission (verdict: Runtime Error):
L, R = [int(i) for i in input().split()]
a = []
for i in range(L, R+1):
    a.append(i % 2019)
    if not i % 2019:
        break
a.sort()
print((a[0]*a[1]) % 2019)


Fixed submission:
import sys


def input():
    return sys.stdin.readline()[:-1]


def main():
    l, r = map(int, input().split())
    if r-l >= 2018:
        print(0)
    else:
        ans = 2222
        n = [i for i in range(l, r+1)]
        for i in range(len(n)):
            for j in range(i+1, len(n)):
                s = n[i]*n[j] % 2019
                if ans > s:
                    ans = s
        print(ans)

        # n = [[i % 2019, i] for i in range(l, r+1)]
        # n.sort(key=lambda x: x[0])
        # print((n[0][1]*n[1][1]) % 2019)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys


def input():
    return sys.stdin.readline()[:-1]


def main():
    n = input()
    if n[1] == n[2] or n[2] == n[3] or n[3] == n[4]:
        print("Bad")

    else:
        print("Good")


if __name__ == "__main__":
    main()


Fixed submission:
import sys


def input():
    return sys.stdin.readline()[:-1]


def main():
    n = input()
    if n[1] == n[2] or n[2] == n[3] or n[1] == n[0]:
        print("Bad")

    else:
        print("Good")


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys
from collections import Counter
input = sys.stdin.readline
N = int(input())
xy = [tuple([int(i) for i in input().split()]) for _ in range(N)]
ary = []
for i, t in enumerate(xy[:-1]):
    x = t[0]
    y = t[1]
    for x2, y2 in xy[i+1:]:
        p = x2-x
        q = y2-y
        ary.append((p, q))
c = dict(Counter(ary))
print(N-max(c.values()))


Fixed submission:
import sys
from collections import Counter
input = sys.stdin.readline
N = int(input())
xy = [tuple([int(i) for i in input().split()]) for _ in range(N)]
ary = []
if N == 1:
    print(1)
    exit()
for i, t in enumerate(xy[:-1]):
    x = t[0]
    y = t[1]
    for x2, y2 in xy[i+1:]:
        ary.append((x2-x, y2-y))
        ary.append((x-x2, y-y2))
c = dict(Counter(ary))
print(N-max(c.values()))
Buggy python submission (verdict: Runtime Error):
    import sys
    n = [int(i) for i in input().split()]
    a = []
    for i in range(n[1]):
        a.append(int(input()))
     
    a.append(n[0]+1)
    a = sorted(list(set(a)))
     
     
    def k(i):
        ans = 1
        pri = 0
        for idx in range(i):
            tmp = ans
            ans += pri
            pri = tmp
        return ans
     
     
    for i in range(1, len(a)):
        if a[i]-a[i-1] == 1:
            print(0)
            sys.exit()
    j = -1
    ans = 1
    for i in a:
        ii = i-j-2
        ans = ans*k(ii)
        j = i
    if len(a) == 1:
        ans = k(n[0])
    print(ans % 1000000007)

Fixed submission:
import sys
n = [int(i) for i in input().split()]
a = []
for i in range(n[1]):
    a.append(int(input()))

a.append(n[0]+1)
a = sorted(list(set(a)))


def k(i):
    ans = 1
    pri = 0
    for idx in range(i):
        tmp = ans
        ans += pri
        pri = tmp
    return ans


for i in range(1, len(a)):
    if a[i]-a[i-1] == 1:
        print(0)
        sys.exit()
j = -1
ans = 1
for i in a:
    ii = i-j-2
    ans = ans*k(ii)
    j = i
if len(a) == 1:
    ans = k(n[0])
print(ans % 1000000007)

Buggy python submission (verdict: Runtime Error):
import sys
n = [int(i) for i in input().split()]
a = []
for i in range(n[1]):
    a.append(int(input()))

a.append(n[0]+1)
a = sorted(list(set(a)))


def k(i):
    if i <= 1:
        return 1
    elif i == 2:
        return 2
    else:
        return k(i-2)+k(i-1)


for i in range(1, len(a)):
    if a[i]-a[i-1] == 1:
        print(0)
        sys.exit()
j = -1
ans = 1
for i in a:
    ii = i-j-2
    ans = ans*k(ii)
    j = i
if len(a) == 1:
    ans = k(n[0])
print(ans % 1000000007)


Fixed submission:
import sys
n = [int(i) for i in input().split()]
a = []
for i in range(n[1]):
    a.append(int(input()))

a.append(n[0]+1)
a = sorted(list(set(a)))


def k(i):
    ans = 1
    pri = 0
    for idx in range(i):
        tmp = ans
        ans += pri
        pri = tmp
    return ans


for i in range(1, len(a)):
    if a[i]-a[i-1] == 1:
        print(0)
        sys.exit()
j = -1
ans = 1
for i in a:
    ii = i-j-2
    ans = ans*k(ii)
    j = i
if len(a) == 1:
    ans = k(n[0])
print(ans % 1000000007)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
i = S.find("ABC")
c = 0
while i >= 0:
    S = "".join([S[:i], "BCA", S[i+3:]])
    i = S.find("ABC")
    c += 1
print(c)


Fixed submission:
S = input()
c = 0
i = 0
ac = 0
while i < len(S):
    if S[i] == "A":
        ac += 1
    elif S[i:i+2] == "BC":
        c += ac
        i += 1
    else:
        ac = 0
    i += 1
print(c)
Buggy python submission (verdict: Runtime Error):
import sys

def input():
    return sys.stdin.readline()[:-1]

def main():
    n,m = map(int,input().split())
    k = []
    s = []
    ans = 0
    
    for _ in range(m):
        tmp = [int(i) for i in input().split()]
        k.append(tmp.pop(0))
        s.append(tmp)

    p = [int(i) for i in input().split()]

    for i in range(2**n):
        tentou=[0]*m
        b = bin(i)[2:].zfill(5)
        for i2 in range(len(s)):
            for i3 in s[i2]:
                if b[i3-1] == "1":
                    tentou[i2]+=1
        tentou = [z % 2 for z in tentou]
        if tentou == p:
            ans+=1
    print(ans)

if __name__ == '__main__':
    main()


Fixed submission:
import sys

def input():
    return sys.stdin.readline()[:-1]

def main():
    n,m = map(int,input().split())
    k = []
    s = []
    ans = 0
    
    for _ in range(m):
        tmp = [int(i) for i in input().split()]
        k.append(tmp.pop(0))
        s.append(tmp)

    p = [int(i) for i in input().split()]

    for i in range(2**n):
        tentou=[0]*m
        b = bin(i)[2:].zfill(n)
        for i2 in range(len(s)):
            for i3 in s[i2]:
                if b[i3-1] == "1":
                    tentou[i2]+=1
        tentou = [z % 2 for z in tentou]
        if tentou == p:
            ans+=1
    print(ans)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import operator

input=sys.stdin.readline

def main():
    n,m = map(int, input().split())
    a = [int(i) for i in input().split()]
    sousa = []
    d = []
    for _ in range(m):
        sousa.append([int(i) for i in input().split()])

    a.sort()
    
    sousa.sort(key=operator.itemgetter(1))

    for i in sousa:
        d.extend([i[1]] * i[0])

    dIdx = len(d) - 1

    for i in range(len(a)):
        if a[i] < d[dIdx]:
            a[i] = d[dIdx]
            dIdx -= 1
            if dIdx < 0:
                break

    print(sum(a))

if __name__ == "__main__":
    main()


Fixed submission:
import sys
import operator

input=sys.stdin.readline

def main():
    n,m = map(int, input().split())
    a = [int(i) for i in input().split()]
    sousa = []
    d = []
    for _ in range(m):
        sousa.append([int(i) for i in input().split()])

    a.sort()
    
    sousa.sort(key=operator.itemgetter(1), reverse = True)

    for i in sousa:
        d.extend([i[1]] * i[0])
        if len(d)>n:
            break

    dIdx = 0
    dLen = len(d)

    for i in range(len(a)):
        if a[i] < d[dIdx]:
            a[i] = d[dIdx]
            dIdx += 1
            if dIdx >= dLen:
                break

    print(sum(a))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import operator

input=sys.stdin.readline

def main():
    n,m = map(int, input().split())
    a = [int(i) for i in input().split()]
    sousa = []
    d = []
    for _ in range(m):
        sousa.append([int(i) for i in input().split()])

    a.sort()
    
    for i in sousa:
        d.extend([i[1]] * i[0])

    d.sort()
    dIdx = len(d) - 1

    for i in range(len(a)):
        if a[i] < d[dIdx]:
            a[i] = d[dIdx]
            dIdx -= 1
            if dIdx < 0:
                break

    print(sum(a))

if __name__ == "__main__":
    main()


Fixed submission:
import sys
import operator

input=sys.stdin.readline

def main():
    n,m = map(int, input().split())
    a = [int(i) for i in input().split()]
    sousa = []
    d = []
    for _ in range(m):
        sousa.append([int(i) for i in input().split()])

    a.sort()
    
    sousa.sort(key=operator.itemgetter(1), reverse = True)

    for i in sousa:
        d.extend([i[1]] * i[0])
        if len(d)>n:
            break

    dIdx = 0
    dLen = len(d)

    for i in range(len(a)):
        if a[i] < d[dIdx]:
            a[i] = d[dIdx]
            dIdx += 1
            if dIdx >= dLen:
                break

    print(sum(a))

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
N, M = [int(i) for i in input().split()]
AB = [[int(i) - 1 for i in input().split()] for _ in range(M)]
ans = [N * (N - 1) // 2]

class UnionFind:
    def __init__(self, element_count):
        self.parent = [i for i in range(element_count)]
        self.counter = [1 for _ in range(element_count)]
    
    def root(self, index):
        p = self.parent[index]
        if index == p:
            return index
        self.parent[index] = self.root(p)
        return self.parent[index]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.parent[y] = x
            self.counter[x] += self.counter[y]
            self.counter[y] = 0
    
    def count(self, index):
        return self.counter[self.root(index)]

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

uf = UnionFind(N)
for a, b in AB[:0:-1]:
    if not uf.is_same(a, b):
        ans.append(ans[-1] - uf.count(a) * uf.count(b))
        uf.unite(a, b)
    else:
        ans.append(ans[-1])
for a in ans[::-1]:
    print(a)

Fixed submission:
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
N, M = [int(i) for i in input().split()]
AB = [[int(i) - 1 for i in input().split()] for _ in range(M)]
ans = [N * (N - 1) // 2]

class UnionFind:
    def __init__(self, element_count):
        self.parent = [i for i in range(element_count)]
        self.counter = [1 for _ in range(element_count)]
    
    def root(self, index):
        root = index
        while root != self.parent[root]:
            root = self.parent[root]
        while index != root:
            index, self.parent[index] = self.parent[index], root
        return root
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.parent[y] = x
            self.counter[x] += self.counter[y]
            self.counter[y] = 0
    
    def count(self, index):
        return self.counter[self.root(index)]

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

uf = UnionFind(N)
for a, b in AB[:0:-1]:
    if not uf.is_same(a, b):
        ans.append(ans[-1] - uf.count(a) * uf.count(b))
        uf.unite(a, b)
    else:
        ans.append(ans[-1])
for a in ans[::-1]:
    print(a)
Buggy python submission (verdict: Runtime Error):
import math
from functools import reduce


N = int(input())
A = [int(i) for i in input().split()]
print(reduce(math.gcd, A))


Fixed submission:
from fractions import gcd
from functools import reduce
N = int(input())
A = [int(i) for i in input().split()]
print(reduce(gcd, A))