Harryxun/stf_run huggingface dataset:
import heapq
from itertools import chain
from operator import mul

exp10 = [10 ** a for a in range(8, -1, -1)]
movables = [{1, 3}, {0, 2, 4}, {1, 5}, {0, 4, 6}, {1, 3, 5, 7}, {2, 4, 8}, {3, 7}, {4, 6, 8}, {5, 7}]

destination = 123456780


def swap(board, move_from, move_to):
    return board + (exp10[move_to] - exp10[move_from]) * (board // exp10[move_from] % 10)


board0 = sum(map(mul, exp10, chain.from_iterable(map(int, input().split()) for _ in range(3))))
p0 = str(board0).index('0')

appeared = {board0}
queue = list((0, move_from, p0, board0) for move_from in movables[p0])
heapq.heapify(queue)

while True:
    total_cost, move_from, move_to, board = heapq.heappop(queue)
    if board == destination:
        print(total_cost)
        break
    new_board = swap(board, move_from, move_to)
    if new_board in appeared:
        continue
    for move_from2 in movables[move_from]:
        if move_from2 != move_to:
            heapq.heappush(queue, (total_cost + 1, move_from2, move_from, new_board))

### FIXED CODE ###

import heapq
from itertools import chain
from operator import mul

exp10 = [10 ** a for a in range(8, -1, -1)]
movables = [{1, 3}, {0, 2, 4}, {1, 5}, {0, 4, 6}, {1, 3, 5, 7}, {2, 4, 8}, {3, 7}, {4, 6, 8}, {5, 7}]

destination = 123456780


def swap(board, move_from, move_to):
    return board + (exp10[move_to] - exp10[move_from]) * (board // exp10[move_from] % 10)


board0 = sum(map(mul, exp10, chain.from_iterable(map(int, input().split()) for _ in range(3))))
p0 = ('0' + str(board0))[-9:].index('0')

appeared = ({board0: 0}, {destination: 0})
queue = []
queue.extend((0, 0, move_from, p0, board0) for move_from in movables[p0])
queue.extend((0, 1, move_from, 8, destination) for move_from in movables[8])
heapq.heapify(queue)

while True:
    total_cost, direction, move_from, move_to, board = heapq.heappop(queue)
    if board in appeared[not direction]:
        print(total_cost + appeared[not direction][board])
        break
    new_board = swap(board, move_from, move_to)
    if new_board in appeared[direction]:
        continue
    appeared[direction][new_board] = total_cost + 1
    for move_from2 in movables[move_from]:
        if move_from2 != move_to:
            heapq.heappush(queue, (total_cost + 1, direction, move_from2, move_from, new_board))
import math
def lcm(x, y):
  return (x * y) // math.gcd(x, y)
A, B, C, D = map(int, input().split(' '))
res = 0
can_dived_c = B // C - (A - 1) // C
can_dived_d = B // D - (A - 1) // D
can_dived_both = B // lcm(C, D) - (A - 1) // lcm(C, D)
res = B - (A - 1) - can_dived_c - can_dived_d + can_dived_both
print(res)

### FIXED CODE ###

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a
def lcm(x, y):
  return (x * y) // gcd(x, y)
A, B, C, D = map(int, input().split(' '))
can_dived_c = B // C - (A - 1) // C
can_dived_d = B // D - (A - 1) // D
can_dived_both = B // lcm(C, D) - (A - 1) // lcm(C, D)
res = B - (A - 1) - can_dived_c - can_dived_d + can_dived_both
print(res)
n = int(input())
count=0

for num in range(n):
    d1,d2 = map(int,input().split())
    if d1 == d2:
        count += 1
else:
    if count>0:
        print("Yes")
    else:
        print("No")v

### FIXED CODE ###

n = int(input())
count=0
flg=0

for num in range(n):
    d1,d2 = map(int,input().split())
    if d1 == d2:
        count += 1
        if count>= 3:
            flg = 1
    else:
        count=0
else:
    if count > 3 or flg >0:
        print("Yes")
    else:
        print("No")
import sympy
n=int(input())
li=[]
f=[sympy.divisor_count(i) for i in range(1,n+1)]

for i in range(1,n+1):
    li.append(i*f[i-1])
print(sum(li))


### FIXED CODE ###

n=int(input())

#L=[n//i*(i+n//i*i)//2 for i in range(1,n+1)]
#print(sum(L))
ans=0
#for i in range(1,n+1):
#    for j in range(1,n+1):
#        if i%j==0:
#            ans+=i
#print(ans)
g=lambda x:(x*(n//x)*(n//x+1))//2
print(sum(g(i) for i in range(1,n+1)))
a=input()
    a=list(a)
    b=input()
    b=list(b)
    n=len(a)
    j=1
    for i in range(n):
      if(a[i]!=b[-(i+1)]):
        j=0
    if(j==1):
      print("YES")
    else:
      print("NO")

### FIXED CODE ###

a=input()
a=list(a)
b=input()
b=list(b)
n=len(a)
j=1
for i in range(n):
  if(a[i]!=b[-(i+1)]):
    j=0
if(j==1):
  print("YES")
else:
  print("NO")
n = int(input())
I = float('inf')
H = [int(i) for i in input().split()]
H1 = [abs(H[i]-H[i-1]) for i in range(1,n)] + [I]
H2 = [abs(H[i]-H[i-2]) for i in range(2,n)] + [I]*2

def dfs(c,a):
    if c >= n - 1:
        return a
    else:
        r1 = dfs(c + 1, a + H1[c])
        r2 = dfs(c + 2, a + H2[c])
        return min(r1,r2)


print(dfs(0,0))


### FIXED CODE ###

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

H1 = [abs(H[i]-H[i-1]) for i in range(1,n)]
H2 = [abs(H[i]-H[i-2]) for i in range(2,n)]

D = [0]*n
D[1] = H1[0]

for i in range(2,n):
    D[i] = min(D[i-1] + H1[i-1], D[i-2] + H2[i-2])

print(D[-1])
for a in range(10):
	for b in range(10):
		i = a x b
		print(a,"x" ,b ,"=",i)
	


### FIXED CODE ###

for a in range(1,10):
	for b in range(1,10):
		i = a * b
		print(a,"x",b,"=",i,sep="")
N, M, *PS = open(0).read().split()
N, M = [int(_) for _ in [N, M]]
cor = [0] * (N + 1)
pen = [0] * (N + 1)
for p, s in PS:
    p = int(p)
    if cor[p] == 1:
        continue
    if s == 'AC':
        cor[p] = 1
    else:
        pen[p] += 1
ans = [0, 0]
for i in range(1, N + 1):
    if cor[p] == 0:
        continue
    ans[0] += 1
    ans[1] += pen[ @ ]
print(*ans)


### FIXED CODE ###

N,M=[int(_) for _ in input().split()]
PS=[input().split() for _ in range(M)]
count=[0]*(N+1)
isac=[0]*(N+1)
for p,s in PS:
 p=int(p)
 if isac[p]==1:
    continue
 if s=='AC':
  isac[p]=1
 else:
  count[p]+=1
wa=0
ac=0
for i in range(N+1):
 if isac[i]==1:
  ac+=1
  wa+=count[i]
print(ac,wa)
n = int(input())
s = input()
l = []
for i in range(1, len(s) - 1):
    f = s[:i]
    b = s[i:]
    fset = list(set(s[:i]))
    bset = list(set(s[i:]))
    cnt = 0
    for j in fset:
        if bset.count(j) != 0:
            cnt += 1
    l.append(cnt)
print(max(l))

### FIXED CODE ###

n = int(input())
s = input()
l = []

for i in range(1, len(s)):
    
    f = s[:i]
    b = s[i:]
    fset = list(set(s[:i]))
    bset = list(set(s[i:]))
    cnt = 0
   
    for j in fset:
        if bset.count(j) != 0:
            cnt += 1
    l.append(cnt)
   
print(max(l))
pattern = {
    0:["#", "."],
    1:[".", "#"],
}

while True:
    (H, W) = [int(i) for i in input().split())]
    if H == W == 0:
        break
    for j in range(H):
        p = pattern[j % 2]
        print (.join([p[i % 2] for i in range(W)]))
        print()

### FIXED CODE ###

while True:
    H, W = [int(i) for i in input().split()]
    if H == W == 0:
        break

    for h in range(H):
        for w in range(W):
            if (h + w) % 2 == 0:
                print('#', end='')
            else:
                print('.', end='')

        print()
    print()
import sys
  lalala = 1000000 // 6 + 1
f = [1, 0, 0, 0, 1, 0] * lalala
f = [0, 0, 1, 1] + f[3:-2]

i = 5
while i < 1000:
    if f[i] == 1:
        j = i * i
        while j <= 1000000:
            f[j] = 0
            j += i + i
    i += 2

for n in sys.stdin:
    i = int(n)
    print(sum(f[:i + 1]))

### FIXED CODE ###

import sys

f = [1, 0, 0, 0, 1, 0] * (1000000 // 6 + 1)
f = [0, 0, 1, 1] + f[3:-2]

i = 5
while i < 1000:
    if f[i] == 1:
        j = i * i
        while j <= 1000000:
            f[j] = 0
            j += i + i
    i += 2

for n in sys.stdin:
    i = int(n)
    print(sum(f[:i + 1]))
a=int(input())
b=int(input())
menseki=a*b
syu=a*2+b*2
print(menseki,syu)

### FIXED CODE ###

l = 0
l = input().split()
men = 0
syu = 0
unko = int(l[0])
tinko = int(l[1])
men = unko*tinko
syu = unko*2+tinko*2
print(men,syu)
def main(A, dq, n):
    if n == -1:
        return dq[0]

    if (n in A) == False: 
        dp[n] = dp[n + 1] + dp[n + 2]
    return main(A, dq, n-1)
 
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * 10**5
A = [int(input()) for _ in range(M)] 
dp[N], dp[N-1] = 1, 1
ans = main(A, dp, N-2)
print(ans % mod)


### FIXED CODE ###

N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (N+2)
A = set([int(input()) for _ in range(M)]) 
dp[-2] = 1

for i in range(N-1, -1, -1):
    if (i in A) == False:
        dp[i] = (dp[i + 1] + dp[i + 2]) % mod 

print(dp[0])
a, b = [int(x) for x in input().split() if x.isdigit()]
if a < b:
    print("a < b")
elif a > b:
    print("a > b")
else:
    print("a == b")

### FIXED CODE ###

a, b = input().split() 
a, b = int(a), int(b)
if a < b:
    print("a < b")
elif a > b:
    print("a > b")
else:
    print("a == b")
t = input()
t = list(t)

if t[0] == "?":
    if t[1] == "P":
        t[0] = "D"
    else:
        t[0] = "P"
        
for i in range(1, len(t) - 1):
    if t[i] == "?":
        if t[i - 1] == "P":
            t[i] = "D"
        else:
            if t[i + 1] == "P":
                t[i] = "D"
            else:
                t[i] = "P"
if t[len(t) - 1] == "?":
        t[len(t) - 1] = "D"
            
                
ans = "".join(t)
print(ans)

### FIXED CODE ###

t = input()
 
ans = t.replace("?", "D")
print(ans)
#パナソニックプロ2020
abc=map(int,input().split())
if a**0.5 +b**0.5 < c**0.5:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

#パナソニックプロ2020
a,b,c=map(int,input().split())
if c-a-b<=0:
    print('No')
elif 4*a*b< (c-a-b)**2:
    print('Yes')
else:
    print('No')
N = int(input())
*A, = map(int,input().split())

A.sort()

for i,a in enumerate(A):
    if a>=0:break
B = A[:i]
C = A[i:]

ans = []
if not B:
    x = C[0]
    for a in C[1:-1]:
        ans.append((x,a))
        x -= a
    ans.append((C[-1],x))
    x = C[-1] - x
else:
    x = B[0]
    for a in C[1:]:
        ans.append((x,a))
        x -= a
    ans.append((C[0],x))
    x = C[0]-x
    for a in B[1:]:
        ans.append(x,a)
        x -= a

print(x)
for out in ans:
    print(*out)

### FIXED CODE ###

N = int(input())
*A, = map(int,input().split())

A.sort()

for i,a in enumerate(A):
    if a>=0:break
B = A[:i]
C = A[i:]

ans = []
if not B:
    x = C[0]
    for a in C[1:-1]:
        ans.append((x,a))
        x -= a
    ans.append((C[-1],x))
    x = C[-1] - x
elif not C:
    x = B[-1]
    for a in B[:-1]:
        ans.append((x,a))
        x -= a
else:
    x = B[0]
    for a in C[1:]:
        ans.append((x,a))
        x -= a
    ans.append((C[0],x))
    x = C[0]-x
    for a in B[1:]:
        ans.append((x,a))
        x -= a

print(x)
for out in ans:
    print(*out)
N = int(input())
ans = 0
for i in N:
  if len(list(i)) % 2 = 1:
    ans += 1
print(ans)
  

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N+1):
  if len(list(str(i))) % 2 == 1:
    ans += 1
print(ans)
X, A = map(int,input().split())
if A//X ==0:
  print(0)
else: print(10)

### FIXED CODE ###

X, A = map(int,input().split())
print(int(X>=A)*10)
r=int(input())
return(3*r^2)

### FIXED CODE ###

r=int(input())
print(3*(r**2))
import math


def main():
    a, b = map(int, input().split())
    ans = "{:.0f}".format(a * b / math.gcd(a, b))
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def gcd(a, b):
    if a > b:
        a, b = (b, a)
    while b:
        a, b = b, a % b
    return a


def main():
    a, b = map(int, input().split())
    ans = round(a * b / gcd(a, b))
    print(ans)


if __name__ == '__main__':
    main()
a,b,c,d = map(int,input().split())

if a < 0 and b < 0 :
    if c <= 0 :
        print(a*c)
    else :
        print(b*c)
elif a < 0 and b == 0:
    if c <= 0:
        print(a*c)
    else :
        print(b*c)
elif a < 0 and b > 0 :
    if d<=0 :
        print(a*c)
    else :
     if a * c < b * d :
        print(b*d)
    else :
        print(a*c)
elif a==0 and b > 0:
    if d <= 0:
        print(0)
    else :
        print(b*d)
elif a > 0 and b > 0:
    if d <= 0:
        print(a*d)
    else :
        print(b*d)

### FIXED CODE ###

a,b,c,d = map(int,input().split())

print(max([a*c,a*d,b*c,b*d]))
import math

n, x = list(map(int, input().split()))
xi = list(map(int, input().split()))

ans = None
for i in xi:
    distance = abs(i-x)
    if ans is None:
        ans = distance
    else:
        ans = math.gcd(ans, distance)
print(ans)

### FIXED CODE ###

import math
import numpy as np
def yakusu(num):
    top = []
    bot = []
    for i in range(int(math.sqrt(num))):
        k = i+1
        if num%k == 0:
            top.append(num//k)
            bot.append(k)
    return top + bot[::-1]

n, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)
x.sort()
start = x[0]
x = np.array(x[1:])
x -= start
# print(x)

for ans_pred in yakusu(x[0]):
    if ans_pred == 1:
        break
    flag = True
    for i in x:
        if i % ans_pred != 0:
            flag= False
            break
    if flag:
        break

print(ans_pred)
l, n = map(int, input().split())

st = []
for _ in range(n):
  st.append(str(input()))

st.sort()
  
print(''.join(st))


### FIXED CODE ###

N, L = map(int, input().split())
list=[]
for i in range(N):
    list.append(str(input()))
list.sort()
print("".join(list))
N = int(input())
S = input()

ns = []

for ch in S:
        
    if ('A' <= ch and ch <= 'Z'):
        ns.append(chr((ord(ch) - ord('A') + N) % 26 + ord('A')))

O = "".join(ns)
print(O)

### FIXED CODE ###

S = input()

mydict = {"SUN":7, "MON":6, "TUE":5, "WED":4, "THU":3, "FRI":2, "SAT":1} 

O = mydict[S]

print(O)
r= map(int,raw_input().split())
pi=3.14
s=float(r)*r*pi
l=float(r)*2*pi

print "%f %f" %(s,l)

### FIXED CODE ###

import math

r= input()
s=math.pi*float(r)**2
l=2*math.pi*float(r)

print "%f %f" %(s,l)
import math
n = int(input())
d = list(map(int,input().split()))
d.sort()
if (len(d))%2 == 0:
  m = (d[(len(d)//2)-1]+d[len(d)//2])/2
else:
  m = d[(len(d)//2)]
p = 0
q = 0
for i in range(len(d)):
  if d[i]>=m:
    if d[i] == d[i+1]:
      break
    else:
      p = d[i]
      q = d[i-1]
      break
print(p-q)

### FIXED CODE ###

n = int(input())
d = sorted(list(map(int,input().split())))
print(d[n//2]-d[n//2-1])
(m, f, r) = [int(i) for i in input().split()]
    if m==-1 and f==-1 and r==-1:
        break

    g = m + f
    if m == -1 or f == -1 or g < 30:
        print('F')
    elif g >= 80:
        print('A')
    elif g >= 65:
        print('B')
    elif g >= 30 or r >= 50:
        print('C')
    else:
        print('D')
~                    

### FIXED CODE ###

while True:
    (m, f, r) = [int(i) for i in input().split()]
    if m == f == r == -1:
        break
 
    total = m + f
    if m == -1 or f == -1 or total < 30:
        print('F')
    elif total < 50 and r < 50:
        print('D')
    elif total < 65:
        print('C')
    elif total < 80:
        print('B')
    else:
        print('A')
_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

if not edge:
    print(k)
else:
    import collections
    import math

    all_edge_map = collections.defaultdict(list)
    for e in edge:
        all_edge_map[e[0]].append(e[1])
        all_edge_map[e[1]].append(e[0])

    root = edge[0]
    visit  = list(all_edge_map[root[0]])
    tree_edge_map = collections.defaultdict(list)
    colored = []
    math.factorial(k - len(all_edge_map[root[0]]) - 1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)

_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = tuple([tuple([int(p) for p in i.split()]) for i in _input[1:n]])

factorial = [0] * (k + 1)
inverse = [0] * (k + 1)
MOD = 1000000007

# Ref: http://keita-matsushita.hatenablog.com/entry/2016/12/05/175024
def mod_pow1(n, k, mod):
    a = 1
    while k:
        if (k & 1) == 1:
            a = (a * n) % mod
        n = (n * n) % mod
        k >>= 1
    return a

# Ref: https://www.smartbowwow.com/2018/10/mod1097.html
def mod_pow2(n, k, mod):
    if k == 0:
        return 1
    if k % 2 == 0:
        a = mod_pow2(n, k // 2, mod)
        return (a * a) % mod
    else:
        return (n * mod_pow2(n, k - 1, mod)) % mod

#mod_pow = mod_pow1
# It's better to use built-in function for speed.
mod_pow = pow

def mod_factorial_inverse(k, mod):
    factorial[0] = 1
    inverse[0] = 1

    # Ref: http://keita-matsushita.hatenablog.com/entry/2016/12/05/184011
    for i in range(1, k + 1):
        factorial[i] = ((i * factorial[i - 1]) % mod) # factrial[i]
        inverse[i] = mod_pow(factorial[i], mod - 2, mod) # inverse[i]
 
total = 1

if not edge:
    print(k)
else:
    all_edge = tuple([[] for _ in range(n + 1)])
    for e in edge:
        all_edge[e[0]].append(e[1])
        all_edge[e[1]].append(e[0])
    all_edge = [set(v) for v in all_edge]

    if [v for v in all_edge if len(v) >= k]:
        print(0)
    else:
        mod_factorial_inverse(k, MOD)

        root = edge[0]
        total = (factorial[k] * inverse[k - len(all_edge[root[0]]) - 1]) % MOD

        def dfs(current, from_):
            global total
            child = all_edge[current]
            if len(child) - 1 > 0:
                total = (total * factorial[k - 2] * inverse[k - 2 - (len(child) - 1)]) % MOD
            for c in child:
                if c != from_:
                    dfs(c, current)
        for c in all_edge[root[0]]:
            dfs(c, root[0])
        print(total)
a=int(input())
b=int(input())

print((a-1)*(b-1))

### FIXED CODE ###

a,b=map(int,input().split())

print((a-1)*(b-1))
import sys
A, B, K = map(int, input().split())

box = list(range(A, B+1))
s = set()

if len(box) < K:
    for i in box:
        print(i)
    sys.exit()

for i in range(K):
    s.add(box[i])
nb = box[len(box) - K:]
for i in range(K):
    s.add(nb[i])

for k in s:
    print(k)


### FIXED CODE ###

A, B, K = map(int, input().split())
L = [A+i for i in range(K) if A+i <= B]
R = [B-i for i in range(K) if B-i >= A]
S = set(L+R)
S = sorted(S)
for v in S:
    print(v)
a , b = input().split()

if a + b > 24:
	print (a + b - 24)
else:
  	print (a + b)


### FIXED CODE ###

a , b = map(int, input().split())
if a+b >= 24:
	print ((a + b) - 24)
else:
  	print (a + b)
from itertools import product

X, Y, Z, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

a1 = []
mXY = min(X, Y)
for i, j in product(A[0:min(mXY, 3000)], B[0:min(mXY, 3000)]):
    a1.append(i + j)
a1.sort(reverse=True)

ans_list = []
for i, j in product(a1[0:min(mXY, 3000)], C[0:min(Z, 3000)]):
    ans_list.append(i + j)
ans_list.sort(reverse=True)

for i in range(K):
    print(ans_list[i])


### FIXED CODE ###

from itertools import product

X, Y, Z, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

a = []
count = 0
for i in range(X):
    for j in range(Y):
        if (i+1)*(j+1) > K:
            break
        for k in range(Z):
            if (i+1)*(j+1)*(k+1) > K:
                break
            a.append(A[i] + B[j] + C[k])

a.sort(reverse=True)

for i in range(K):
    print(a[i])
i = input().split()
x = list(map(int,i))
W = x[0]
H = x[1]
x = x[2]
y = x[3]
r = x[4]

if W >= x + r and H >= y + r:
   print("Yes")
else:
   print("No")

### FIXED CODE ###

xmas = input().split()
W = int(xmas[0])
H = int(xmas[1])
x = int(xmas[2])
y = int(xmas[3])
r = int(xmas[4])

if W >= (x + r) and H >= (y + r) and (x - r) >= 0 and (y - r) >= 0:
   print("Yes")
else:
   print("No")
n = input()
a = map(int,input(). split ())

d=1

for b in a:
  d=b*d
  if d>10**18:
     print("-1")
      break
    
      
      
      
if d>10**18:
  print("-1")
else:
  print(d) 

### FIXED CODE ###

def main():

	n=input()
	a=list(map(int,input().split()))
	
	
	if 0 in a:
		print(0)
		return

	d=1
    
	

	for b in a:
		d=d*b
		if d>10**18:
			print("-1")
			return
	print(d)

main()
import sys

class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]


n, m = map(int, input().split())
A=[[int(i)-1 for i in input().split()] for _ in range(m)]
bridges.reverse()
buf = [n * (n - 1) // 2]
uft = UnionFind(n)
for line in bridges[:-1]:
    a, b = map(int, line.split())
    if uft.issame(a, b):
        buf.append(buf[-1])
        continue
    ra = uft.size(a)
    rb = uft.size(b)
    buf.append(buf[-1] - ra * rb)
    uft.merge(a, b)
buf.reverse()
print('\n'.join(map(str, buf)))
    
    
    
    
    





### FIXED CODE ###

class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]


n,m=[int(i) for i in input().split()]

A=[[int(i)-1 for i in input().split()] for _ in range(m)]

ans = [0]*(m+1)
a = n*(n-1)//2
ans[0] = a

uf = UnionFind(n)
for i in range(m):
    j = m-i-1
    v1 = A[j][0]
    v2 = A[j][1]
#    print(v1,v2)
    if not uf.issame(v1,v2):
#        print(uf.parent)
        a -= uf.size(v1) * uf.size(v2)
        uf.merge(v1,v2)

    ans[i+1]=a

for i in range(m):
    print(ans[m-i-1])
X,Y = int(input.split(' '))
print(X + (Y/2))

### FIXED CODE ###

X,Y = input().split(' ')
x = int(X)
y = int(Y)

print(x + (y//2))
N, M, X = map(int, input().split())
Ca = [list(map(int, input().split())) for _ in range(N)]
pattern = []
for i in range(2**N):
    lis = []
    for j in range(N):
        if ((i>>j)&1):
            lis.append(Ca[j])
    pattern.append(lis)

cnt = []
for i in range(2**N):
    g = [0]*M
    for j in range(len(pattern[i])):
        for k in range(M+1):
            g[k] += pattern[i][j][k]
    if g[1]<X or g[2]<X or g[3]<X:
        continue
    else:
        cnt.append(g[0])
print(min(cnt))

### FIXED CODE ###

N, M, X = map(int, input().split())
Ca = [list(map(int, input().split())) for _ in range(N)]
pattern = []
for i in range(2**N):
    lis = []
    for j in range(N):
        if ((i>>j)&1):
            lis.append(Ca[j])
    pattern.append(lis)

cnt = []
for i in range(2**N):
    g = [0] * (M+1)
    for j in range(len(pattern[i])):
        for k in range(M+1):
            g[k] += pattern[i][j][k]
    if M==1 and g[1]< X:
        continue
    elif M>1 and min(g[1:M+1]) < X:
        continue
    else:
        cnt.append(g[0])
if len(cnt) ==0:
    print(-1)
else:
    print(min(cnt))