Harryxun/stf_run huggingface dataset:
from collections import deque
n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))
BC=sorted([list(map(int,input().split())) for i in range(m)],key=lambda x:x[1])

cnt=0
A=deque(A)
for b,c in BC[::-1]:
    if len(A)==0:break
    for i in range(b):
        if A[0]<c:
            cnt +=c
            A.popleft()
        else:break
print(cnt+sum(A))

### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))
BC=sorted([list(map(int,input().split())) for i in range(m)],key=lambda x:x[1])

A=deque(A)
for b,c in BC[::-1]:
    if len(A)==0:break
    for i in range(b):
        if A[0]<c:
            A.append(c)
            A.popleft()
        else:break
print(sum(A))
N, X = map(int, input().split())
li = list(map(int, input().split()))
i = 0
D = 0
while D <= X:
    if i > N + 1:
        break
    D += li[i]
    i += 1

if i > N + 1:
    print(N+1)
else:
    print(i)


### FIXED CODE ###

N, X = map(int, input().split())
li = list(map(int, input().split()))
D = [0]*(N+1)
flag = "0"
for i in range(N):
    D[i+1] = D[i] + li[i]
    if D[i+1] > X:
        flag = "1"
        break
if flag == "1":
    print(i + 1)
else:
    print(N + 1)
N, X = map(int, input().split())
steps = list(int,input().split())
 
x = 0
count = 1

for i in steps:
    x += i
    if x <= X:
        count += 1
 
print(count)

### FIXED CODE ###

N, X = map(int, input().split())
steps = list(map(int,input().split()))
 
x = 0
count = 1

for i in steps:
    x += i
    if x <= X:
        count += 1
 
print(count)
n,m=map(int,input().split())
if n==1:
  if m==0:
    print(0)
    exit()
  Q=[]
  for i in range(m):
    _,q=map(int,input().split())
    Q.append(q)
  if len(set(Q)) in [2,3,4,5,6,7]:
    print(-1)
    exit()
  print(min(Q))
  exit()

A=[[1,2,3,4,5,6,7,8,9]]+ [[0,1,2,3,4,5,6,7,8,9]]*(n-1)
for i in range(m):
  k,q=map(int,input().split())
  if k==1 and q==0:
    print(-1)
    exit()
  if not q in A[k-1]:
    print(-1)
    exit()
          
  A[k-1]=[q]
for i in range(n):
  A[i]=min(A[i])
ans=""
for i in range(n):
  ans+=str(A[i])
print(ans)
n,m=map(int,input().split())
if n==1:
  Q=[]
  for i in range(m):
    _,q=map(int,input().split())
    Q.append(q)
  if len(set(Q))!=1:
    print(-1)
    exit()
  print(min(Q))
  exit()

A=[[1,2,3,4,5,6,7,8,9]]+ [[0,1,2,3,4,5,6,7,8,9]]*(n-1)
for i in range(m):
  k,q=map(int,input().split())
  if k==1 and q==0:
    print(-1)
    exit()
  if not q in A[k-1]:
    print(-1)
    exit()
          
  A[k-1]=[q]
for i in range(n):
  A[i]=min(A[i])
ans=""
for i in range(n):
  ans+=str(A[i])
print(ans)


### FIXED CODE ###

n,m=map(int,input().split())
if n==1:
    A=[i for i in range(10)]
    for i in range(m):
        _,c=map(int,input().split())
        if not c in A:
            print(-1)
            exit()
        else:A=[c]
    print(min(A))

if n==2:
    A=[[i+1 for i in range(9)] , [i for i in range(10)]]
    for i in range(m):
        t,c=map(int,input().split())
        t=t-1
        if not c in A[t]:
            print(-1)
            exit()
        else: 
            A[t]=[c]
    print(10*min(A[0]) + min(A[1]))

if n==3:
    A=[[i+1 for i in range(9)] ,[i for i in range(10)] ,[i for i in range(10)]]
    for i in range(m):
        t,c=map(int,input().split())
        t=t-1
        if not c in A[t]:
            print(-1)
            exit()
        else: 
            A[t]=[c]
    print(100*min(A[0]) + 10*min(A[1]) + min(A[2]))
N, H, W = input(), input(), input()
print((N-H+1)*(N-W+1))

### FIXED CODE ###

N = int(input())
H = int(input())
W = int(input())
print((N-H+1)*(N-W+1))
a = int(input())

b = list(map(int,input().split()))
d = max(b)
c = [0 for i in range(pow(10,6)+1)]
cc = [0 for i in range(pow(10,6)+1)]
for i in range(len(b)):
    if i % 2 == 0:
        cc[b[i]-1] += 1
    else:
        c[b[i]-1] += 1

one = 0
onee = 0
two = 0
twoo = 0
k = 0
kk = 0
for i in range(len(c)):
    if one <= c[i]:
        onee = one
        one = c[i]
        k = i
    if two <= cc[i]:
        twoo = two
        two = cc[i]
        kk = i

t = max(one+twoo,onee+two)

if k != kk:
    print(a-one-two)
else:
    print(a-t)


### FIXED CODE ###

a = list(input())
for i in range(3):
	a[i] = int(a[i])
	if a[i] ==1:
		a[i] = 9
	else:
		a[i] = 1
print(a[0]*100+a[1]*10+a[2])
n = int(input())
ai = list(map(int,input().split()))

dp = [[]]

def dp(i, j):
	if i==0 and j==0:
		return 0
	elif i == 0 and j==1:
		return -10**11
	elif j ==0:
		return max(dp(i-1,0)+ai[i-1], dp(i-1,1)-ai[i-1])
	else:
		return max(dp(i-1,0)-ai[i-1], dp(i-1,1)+ai[i-1])

print(dp(n,0))

### FIXED CODE ###

n = int(input())
ai = list(map(int,input().split()))

dp =[[0, -10**9]]
#print(dp[0][0])

for i in range(1,n+1):
	dp.append([max(dp[i-1][0]+ai[i-1], dp[i-1][1]-ai[i-1]), \
			max(dp[i-1][0]-ai[i-1], dp[i-1][1]+ai[i-1])])
	#print(dp)
    
print(dp[n][0])
D, G = list(map(int, input().split(' ')))
left = {}
bonus = {}
for i in range(1, D+1):
    left[i], bonus[i] = list(map(int, input().split(' ')))

big = 9999999

probably_ans = big
def hogehoge(depth, index, pt, left, bonus, probably_ans):
    if depth >= probably_ans:  # 遅いかも
        return big
    if pt >= G:
        return depth
    for i in range(index, D+1):
        if left[i] == 0:
            continue
        left[i] = left[i] - 1
        probably_ans = min(probably_ans, hogehoge(depth+1, i, pt + i * 100 + bonus[i] * (left[i] == 0), left, bonus, probably_ans))
        left[i] = left[i] + 1
    return probably_ans
    
print(hogehoge(0, 1, 0, left, bonus, probably_ans))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)
D, G = list(map(int, input().split(' ')))
left = {}
bonus = {}
for i in range(1, D+1):
    left[i], bonus[i] = list(map(int, input().split(' ')))
 
big = 9999999
 
probably_ans = big
memo = {}
def hogehoge(depth, index, pt, left, bonus, probably_ans):
    key = (depth, index, pt, str(left))
    if key in memo:
        return memo[key]
    if pt >= G:
        return depth
    if depth >= probably_ans or index > D:  # 遅いかも
        return big
    
    # 一つも引かない
    probably_ans = min(probably_ans, hogehoge(depth, index + 1, pt, left, bonus, probably_ans))
    
    # 全部引いて index reset
    for k in range(0, D - index + 1):
        if left[index + k]:
            temp = left[index + k]
            left[index + k] = 0
            probably_ans = min(probably_ans, hogehoge(depth+temp, 1, pt + (index + k) * 100 * temp + bonus[index + k], left, bonus, probably_ans))
            left[index + k] = temp

    # 歯抜け状態から行けそうならクリア
    if left[index]:
        if pt + index * 100 * left[index] + bonus[index] >= G:
            for i in range(1, left[index] + 1):
                left[index] = left[index] - i
                new_pt = pt + index * 100 * i + bonus[index] * (left[index] == 0)
                if (new_pt >= G):
                    probably_ans = min(probably_ans, hogehoge(depth+i, index+1, new_pt, left, bonus, probably_ans))
                left[index] = left[index] + i
    memo[key] = probably_ans
    return probably_ans
    
print(hogehoge(0, 1, 0, left, bonus, probably_ans))
n = int(input())
s = ["" for _ in range(n)]
for i in range(n):
    s[i] = str(input())
march = ["M","A","R","C","H"]
march_num = [0,0,0,0,0]
for i in range(n):
    if s[i][0] in march:
        march_num[march.index(s[i][0])] += 1
ans = 0
for i in range(len(s)-2):
    for j in range(i+1,len(s)-1):
        for k in range(j+1,len(s)):
            ans += (march_num[i]*march_num[j]*march_num[k])
print(ans)

### FIXED CODE ###

n = int(input())
s = ["" for _ in range(n)]
for i in range(n):
    s[i] = str(input())
    s[i] = s[i][0]

march = ["M","A","R","C","H"]
march_num = [0,0,0,0,0]

for i in range(len(s)):
    if s[i] in march:
        march_num[march.index(s[i])] += 1
ans = 0
for i in range(3):
    for j in range(i+1,4):
        for k in range(j+1,5):
            ans += (march_num[i]*march_num[j]*march_num[k])
print(ans)
n, m = map(int, input().split())
a = list(map(int, input().split()))

for i in range(n):
    a[i] = a[i]/2
    

def calc(n):
    ret = 0
    while n%2 == 0:
        ret +=1
        n/=2
    return ret


flag = True
t = 0
for i in range(n-1):
    t = 2**calc(a[i])
    if calc(a[i]) == calc(a[i+1]):
        continue
    else:
        flag = False
        print(0)
        exit()

a = [a[i]//t for i in range(n)]

def gcd(a, b):
    if a%b == 0:
        return b
    else:
        return gcd(b, a%b)

gcd_a = a[0]
for i in range(1,n):
    p = max(gcd_a, a[i])
    q = min(gcd_a, a[i])
    gcd_a = gcd_a*a[i]//gcd(p, q)
# print("gcd_a", gcd_a)

if flag:
    if (m//gcd_a)%2 == 0:
        print(int((m//gcd_a)//2))
    else:
        print(int((m//gcd_a+1)//2))

else:
    print(0)


### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))

for i in range(n):
    a[i] = a[i]//2
    
# print(a)
def calc(n):
    ret = 0
    while n%2 == 0:
        ret +=1
        n//=2
    return ret


flag = True
t = 0
for i in range(n-1):
    t = 2**calc(a[i])
    if calc(a[i]) == calc(a[i+1]):
        # print(calc(a[i]),calc(a[i+1]))
        continue
    else:
        flag = False
        break


def gcd(a, b):
    if a%b == 0:
        return b
    else:
        return gcd(b, a%b)



if flag:
    lcm = 1
    for i in range(n):
        p = max(lcm, a[i])
        q = min(lcm, a[i])
        lcm = lcm*a[i]//gcd(p, q)
        # print(lcm)
    if (m//lcm)%2 == 0:
        print(int((m//lcm)//2))
    else:
        print(int((m//lcm+1)//2))

else:
    print(0)
n = int(input())
a = [int(x) for x in input().split()]
ans = 0
for i in range(n):
  if i == n-1 and a[i] == n:
    ans += 1
  if a[i] == i+1:
    ans += 1
    a[i], a[i+1] = a[i+1], a[i]
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
ans = 0
for i in range(n):
  if i == n-1 and a[i] == n:
    ans += 1
  elif a[i] == i+1:
    ans += 1
    a[i], a[i+1] = a[i+1], a[i]
print(ans)
a, b = map(int, input().split(" "))
for i in range(1, 10000):
    if int(i * 0.08) == a and int(i * 0.1) == b:
        print(i)
        return
print(-1)

### FIXED CODE ###

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

found = False
for i in range(1, 10000):
    if int(i * 0.08) == a and int(i * 0.1) == b:
        print(i)
        found = True
        break

if not found:
    print(-1)
x,a = map(int,input().split())
    if x < a:
        print(0)
    else : 
        print(10)

### FIXED CODE ###

x,a = map(int,input().split())
if x < a:
  print(0)
else : 
  print(10)
age = int(input())

if age == 1:
    print(Hello World)
else:
    a = int(input())
    b = int(input())
    print(a + b)

### FIXED CODE ###

age = int(input())

if age == 1:
    print("Hello World")
else:
    a = int(input())
    b = int(input())
    print(a + b)
import math
a = input()
print(str(2a*math.pi))

### FIXED CODE ###

import math
a = int(input())
print(str(2*a*math.pi))
import numpy as np
N = int(input())
A = list(map(int, input().split()))
newA = np.array(A)
num = np.gcd.reduce(newA)
print(num)

### FIXED CODE ###

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


N = int(input())
A = list(map(int, input().split()))
num = A[0]
for i in range(N):
    num = gcd(num, A[i])
print(num)
if abs(x) == abs(y):
    print(1)
    exit()
if x * y < 0:
    print(abs(abs(x) - abs(y)) + 1)
elif x == 0 or y == 0:
    print(max(abs(x), abs(y)))
elif x < y:
    print(y - x)
elif y > 0:
    print(x + y + 2)
else:
    print(abs(y) - abs(x) + 2)

### FIXED CODE ###

x, y = map(int, input().split())
ans = float('inf')
if x <= y:
    ans = min(ans, y - x)
if (-1) * x <= y:
    ans = min(ans, y + x + 1)
if x <= (-1) * y:
    ans = min(ans, -y - x + 1)
if (-1) * x <= (-1) * y:
    ans = min(ans, -y + x + 2)
print(ans)
r, g = int(input()).split()
print(2 * g - r)

### FIXED CODE ###

r = int(input())
g = int(input())

print(2 * g - r)
n,k=map(int,input().split())
s=input()
num=[0]
c=1
for i in range(1,n):

    if s[i]==s[i-1]:
        c+=1
    else:
        num.append(c)
        c=1
num.append(c)
num.append(0)
#print(num)

ans=0
#print(num)
if s[0]=="0":
    if len(num)-2*k+1<=0:
        ans=sum(num)
    else:
        asum=sum(num[0:2*k+1])
        ans=asum
        #print(asum)
        for i in range(2,len(num)-2*k,2):
            #print(asum,num[i+2*k],num[i+2*k-1],num[i-1],num[i-2])
            asum=asum+num[i+2*k]+num[i+2*k-1]-num[i-1]-num[i-2]
            ans=max(ans,asum)
if s[0]=="1":
    if len(num)-2*k+2<=0:
        ans=sum(num)
    else:
        asum=sum(num[1:2*k+2])
        ans=asum
        for i in range(3,len(num)-2*k+1,2):
            #print(asum,num[i+2*k],num[i+2*k-1],num[i-1],num[i-2])
            asum=asum+num[i+2*k]+num[i+2*k-1]-num[i-1]-num[i-2]
            ans=max(ans,asum)
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
s=input()
num=[0]
c=1
for i in range(1,n):

    if s[i]==s[i-1]:
        c+=1
    else:
        num.append(c)
        c=1
num.append(c)
num.append(0)
#print(num)

ans=0
#print(num)
if s[0]=="0":
    if len(num)-2*k+1<=0:
        ans=sum(num)
    else:
        asum=sum(num[0:2*k+1])
        ans=asum
        #print(asum)
        for i in range(2,len(num)-2*k,2):
            #print(asum,num[i+2*k],num[i+2*k-1],num[i-1],num[i-2])
            asum=asum+num[i+2*k]+num[i+2*k-1]-num[i-1]-num[i-2]
            ans=max(ans,asum)
if s[0]=="1":
    if len(num)-2*k+2<=0:
        ans=sum(num)
    else:
        asum=sum(num[1:2*k+2])
        ans=asum
        for i in range(3,len(num)-2*k,2):
            #print(asum,num[i+2*k],num[i+2*k-1],num[i-1],num[i-2])
            asum=asum+num[i+2*k]+num[i+2*k-1]-num[i-1]-num[i-2]
            ans=max(ans,asum)
print(ans)
n, k, x, y = map(int, input().split())
if n <= k:
  print(n * x)
else:
  print(k * x + (n - k) * y)

### FIXED CODE ###

n = int(input())
k = int(input())
x = int(input())
y = int(input())
if n <= k:
  print(n * x)
else:
  print(k * x + (n - k) * y)
N = int(input())
inp = [input() for i in range(N)]

import numpy as np

s_list = []
p_list = []
#sp_list = []
for i in inp:
    s_list.append(i.split()[0])
    p_list.append(int(i.split()[1]))
    #sp_list.append(i.split())
sp_list = []
for i in range(N):
    sp_list.append([s_list[i],p_list[i]])

# 市を辞書順
sort_sp_list = sorted(sp_list)

# 市の種類
s_type = sorted(list(set(s_list)))
tmp_list = []
for type in s_type:
    tmp_list.append(sorted([s for s in sort_sp_list if s[0] == type],reverse=True))
rank_list = np.array(tmp_list).reshape(N,2).tolist()

for i in [i.split() for i in inp]:
    print(rank_list.index(i)+1)


### FIXED CODE ###

N = int(input())
inp = [input() for i in range(N)]

import numpy as np

s_list = []
p_list = []
for i in inp:
    s_list.append(i.split()[0])
    p_list.append(int(i.split()[1]))

sp_list = []
for i in range(N):
    sp_list.append([s_list[i],p_list[i]])

# 市を辞書順
sort_sp_list = sorted(sp_list)

# 市の種類
s_type = sorted(list(set(s_list)))
tmp_list = []
for type in s_type:
    tmp_list.append(sorted([s for s in sort_sp_list if s[0] == type],reverse=True))

rank_list = []
for tmp in tmp_list:
    for l in tmp:
        rank_list.append(l)

for rank in rank_list:
    print(sp_list.index(rank)+1)
def quick_sort2(a, i, j):
    if j <= i:
        pass
    else:
        p = a[j]; s = i
        for k in range(i, j):
            if a[k] <= p:
                a[s], a[k] = a[k], a[s]
                s += 1

        a[j], a[s] = a[s], a[j]
        quick_sort2(a, i, s-1)
        quick_sort2(a, s+1, j)


n = int(raw_input())
A = map(int, raw_input().split())

quick_sort2(A, 0, n - 1)

print " ".join(map(str, A))

### FIXED CODE ###

n = int(raw_input())
x = map(int,raw_input().split())
x.sort()
for i in xrange(n):
	print x[i],
N =[1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,14,1,5,1,5,2,2,1,15,2,2,5,4,1,4,1,51]
K =int(input())
print(N[K+1])

### FIXED CODE ###

N =[1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,14,1,5,1,5,2,2,1,15,2,2,5,4,1,4,1,51]
K =int(input())
print(N[K-1])
_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]]

import collections

colored  = {}
edge_map = collections.defaultdict(list)
for e in edge:
    edge_map[e[0]].append(e[1])
    edge_map[e[1]].append(e[0])

root = edge[0][0]
colored[root] = k
for i, p in enumerate(edge_map[root]):
    colored[p] = k - (i + 1)

visit = []
visit.extend(edge_map[root])
while visit:
    current = visit.pop(0)
    not_colored = [p for p in edge_map[current] if p not in colored]
    visit = not_colored + visit
    for i, p in enumerate(not_colored):
        colored[p] = k - (i + 2)

total = 1
for i in colored.values():
    total *= i
    if total > 1000000007:
        total %= 1000000007
print(total)


### 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)
N = int(input())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]
def_Bsum = sum(B)
 
for i in range(N+1):
    if(i==0):
        if (A[i] < B[i]):
            B[i] -= A[i]
            A[i] = 0
        else:
            A[i] -= B[i]　　　　　　　　#倒せたら０にする。最後引いた時に残るように。
            B[i] = 0
 
    if(0<i<N):
        if(A[i] < B[i-1]):
            B[i-1] -= A[i]
            A[i] = 0
        else:
            A[i] -= B[i-1]
            B[i-1] = 0
 
            if (A[i] < B[i]):
                B[i] -= A[i]
                A[i] = 0
            else:
                A[i] -= B[i]
                B[i] = 0
 
    if(i==N):
        if (A[i] < B[i-1]):
            B[i-1] -= A[i]
            A[i] = 0
        else:
            A[i] -= B[i-1]
            B[i-1] = 0
 
 
ans = def_Bsum - sum(B)

print(ans)

### FIXED CODE ###

N = int(input())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]
def_Bsum = sum(B)
 
for i in range(N+1):
    if(i==0):                  #倒せたら０にする。最後に引いたら残るように
        if (A[i] < B[i]):
            B[i] -= A[i]
            A[i] = 0
        else:
            A[i] -= B[i]
            B[i] = 0
 
    if(0<i<N):
        if(A[i] < B[i-1]):
            B[i-1] -= A[i]
            A[i] = 0
        else:
            A[i] -= B[i-1]
            B[i-1] = 0
 
            if (A[i] < B[i]):
                B[i] -= A[i]
                A[i] = 0
            else:
                A[i] -= B[i]
                B[i] = 0
 
    if(i==N):
        if (A[i] < B[i-1]):
            B[i-1] -= A[i]
            A[i] = 0
        else:
            A[i] -= B[i-1]
            B[i-1] = 0
 
 
ans = def_Bsum - sum(B)

print(ans)
N = int(input())
L = [int(input()) for i in range(N)]
print('Yes' if sum(L)-max(L) > max(L) else 'No')

### FIXED CODE ###

input()
L = list(map(int, input().split()))
print("Yes" if sum(L) > 2*max(L) else "No")
N, M = map(int, input().split())

B = [list(map(int, input().split())) for _ in range(M)][::-1]

class Group:
    id = 0
    def __init__(self):
        self.id = Group.id
        Group.id += 1
        self.root = None
        self.children = []
        self.count = 2

    def top(self):
        w = self
        while not w.root is None:
            w = w.root
        return w

    def addMember(self):
        self.count += 1

    def union(self, g):
        self.top().count += g.top().count
        self.top().children.extend(g.top().children)
        ch = g.top().children
        for x in ch:
            x.root = self.top()
        g.top().root = self.top()

    def __repr__(self):
        w = self.top()
        return str(("Gropup", w.id, w.count))

pt = []
G = [None] * (N+1)
idx = 0
cnt = 0
for x, y in B:
    wx = G[x]
    wy = G[y]
    wcnt = (wx is None) + (wy is None)

    if wcnt >= 2:
        pt.append(1)
        w = Group()
        G[x] = w
        G[y] = w
    elif wcnt == 1:
        if wx is None:
            wx = wy
            G[x] = G[y]
        else:
            G[y] = G[x]
        pt.append(wx.top().count)
        wx.addMember()
    else:
        if wx.top() is wy.top():
            pt.append(0)
        else:
            pt.append(wx.top().count * wy.top().count)
            wx.union(wy)

    print(G)

cnt = 0
for x in pt[::-1]:
    cnt += x
    print(cnt)


### FIXED CODE ###

N, M = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(M)]

pt = []
G = [[None, 1] for x in range(N+1)]

def find(x):
    n = G[x]
    c = []
    while not n[0] is None:
        c.append(n)
        n = n[0]
    for ci in c:
        ci[0] = n
    return n

cnt = 0
while len(B):
    x, y = B.pop()
    wx = find(x)
    wy = find(y)
    if wx is wy:
        pt.append(0)
    else:
        pt.append(wx[1] * wy[1])
        wx[1] += wy[1]
        wy[0] = wx

    #print(G)

cnt = 0
for _ in range(M):
    cnt += pt.pop()
    print(cnt)