Harryxun/stf_run huggingface dataset:
A,B = map(int,input().split())
def gcd(a,b):
    if a<b : a,b = b,a
    if b==0: return a
    else: return gcd(b, a%b)
C = gcd(A,B)
ans = 0
X = [True]*(C+1)
X[0] = X[1] = False
for i in range(C+1):
    if X[i]:
        X[i::i] = [False]*(C//i)
        if C%i==0: ans+=1
print(ans+1)

### FIXED CODE ###

import math,sys
sys.setrecursionlimit(1000000)
def mygcd(x,y):
    if x<y:x,y=y,x
    if y==0:return x
    return mygcd(y,x%y)
def is_prime(n):
    if n==1:return True
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:return False
    return True
A,B = map(int,input().split())
gcd = mygcd(A,B)
C = []
for i in range(1,gcd+1):
    if i*i>gcd:break
    if gcd%i==0:
        C.append(i)
        if i!=gcd//i:
            C.append(gcd//i)
cnt = 0
for c in C:
    if is_prime(c):cnt+=1
print(cnt)
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]

f = [0 for i in range(N)]
f[0] = 1
f[1] = 1

for i in range(2,N):
    if i in a:
        continue
    else:
        f[i] = f[i-1]+f[i-2]
        
print(f[N-1]+f[N-2])

### FIXED CODE ###

import sys
import numpy as np
MOD = 1000000007
def main():
    n, m = [int(x) for x in input().split()]
    pattern = [1]
    broken = -1
    brokencnt = 0
    if brokencnt < m:
        broken = int(input())
        brokencnt += 1
    for i in range(1, n + 1):
        if i == broken:
            pattern.append(0)
            if brokencnt < m:
                broken = int(input())
                brokencnt += 1
            continue
        if i == 1:
            pattern.append(pattern[i - 1])
        if i > 1:
            pattern.append((pattern[i - 1] + pattern[i - 2]) % MOD)
    print(pattern[n])
main()
n,m = map(int,input().split())
alis = list(map(int,input().split()))
lis = [list(map(int,input().split())) for x in range(m)]
clis = [[x[1]]*x[0] for x in lis]
clis = [x for y in clis for x in y]
clis.sort(reverse=True)
alis.sort()
ans_lis=[x if x>=y else y for x,y in zip(alis,clis)]
if len(clis) < len(alis):
    ans__ = sum(alis[len(clis):])
    ans_=sum(ans_lis)
    print(ans_+ans__)
    print(a)
else:
    print(sum(ans_lis))


### FIXED CODE ###

n,m = map(int,input().split())
alis = list(map(int,input().split()))
lis = [list(map(int,input().split())) for x in range(m)]
for x in alis:
    lis.append([1,x])
lis.sort(reverse=True,key=lambda x:x[1])
ans = 0
for x in lis:
    (number,point) = x
    if number >= n:
        number = n
        ans += number * point
        #print(n)
        #print(ans,'+=',number,'*',point)
        break
    ans += number * point
    n -= number
    #print(n)
    #print(ans,'+=',number,'*',point)
print(ans)
#print(lis)
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0
min = 0
i = 0
j = 0
while min <= K:
	if (i < N) or (j < M):
		if (i < N) and (j < M):
			if A[i]<=B[j]:
				min = min+A[i]
				i = i+1
				ans = ans+1
			else:
				min = min+B[j]
				j = j+1
				ans = ans+1
		elif (i == N):
				min = min+B[j]
				j = j+1
				ans = ans+1
		else:
				min = min+A[i]
				i = i+1
				ans = ans+1
	else:
		ans = ans+1
		break
ans = ans-1
print(ans)

### FIXED CODE ###

a = int(input())
print(a+a*a+a*a*a)
def main():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        tree[a].append(b)
    op = []
    for _ in range(q):
        p, x = map(int, input().split())
        p -= 1
        op.append((p, x))
    
    cntr = [0 for _ in range(n)]
    
    def dfs(node, p):
        lng = len(tree[node])
        cntr[node] += p
        if lng == 0:
            return
        for i in range(lng):
            next_node = tree[node][i]
            dfs(next_node, p)

    for node, p in op:
        dfs(node, p)
    for i in range(n):
        if i == n-1:
            print(cntr[i])
        else:
            print(cntr[i], end=' ')
main()


### FIXED CODE ###

#python3
from collections import deque 
def main():
    n, q = map(int, input().split())
    to = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        to[a].append(b)
        to[b].append(a)

    node = [0 for _ in range(n)]

    for _ in range(q):
        p, x = map(int, input().split())
        node[p-1] += x

    dq = deque() 
    dq.append(0)
    done = [0 for _ in range(n)]
    done[0] = 1
    while len(dq) > 0:
        x = dq.popleft()
        for i in to[x]:
            if done[i] == 1:
                continue
            node[i] += node[x]
            done[i] = 1 
            dq.append(i)

    for i in range(n):
        print(node[i]) if i == n-1 else print(node[i], end=' ')
main()
N, K = input().split()
h = list(map(int, input().split()))
count = [i for i in h if i >= K]
print(len(count))

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
count = [i for i in h if i >= K]
print(len(count))
X = int(input())
ans = 0
ans += X//500 * 1000
x = x % 500
ans += X // 500 * 5

print(ans)

### FIXED CODE ###

X = int(input())
ans = 0
ans += X//500 * 1000
X = X % 500
ans += X // 5 * 5

print(ans)
a = int(input())
b = sorted(list(map(int,input().split())))
for i in range(a):
  if a == 0 :
    c = b[0]
  else:
    c = (b[i]+c)/2
print(c)

### FIXED CODE ###

a = int(input())
b = sorted(list(map(int,input().split())))
for i in range(a):
  if i == 0 :
    c = b[0]
  else:
    c = (b[i]+c)/2
print(c)
def lcs(s1, s2):
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if chr_idx:
                dp.append(chr_idx)
    return len(dp)

def solve():
    N = int(input())
    for _ in range(N):
        x = input()
        y = input()
        print(lcs(x, y))

if __name__ == '__main__':
    solve()

### FIXED CODE ###

S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)
def getLastMatch(s,t):
    for i in range(len(s)-len(t), -1, -1):
        if s[i] == '?' or s[i] == t[0]:
            match = True
            for j in range(len(t)):
                if s[i+j] == '?': continue
                if s[i+j] != t[j]:
                    match = False
                    break
            if match: return i
    return -1

s,t = input(), input()
lastMatch = getLastMatch(s,t)
if lastMatch == -1:
    print('UNRESTORABLE')
else:
    for i in range(len(s)):
        if i >= lastMatch:
            print(t[i-lastMatch],end='')
            continue
        
        if s[i] == '?': print('a',end='')
        else: print(s[i],end='')
    print()



### FIXED CODE ###

def getLastMatch(s,t):
    for i in range(len(s)-len(t), -1, -1):
        if s[i] == '?' or s[i] == t[0]:
            match = True
            for j in range(len(t)):
                if s[i+j] == '?': continue
                if s[i+j] != t[j]:
                    match = False
                    break
            if match: return i
    return -1

def getS(s,t,lastMatch):
    s = list(s)
    for i in range(len(t)):
        s[i+lastMatch] = t[i]
    for i in range(len(s)):
        if s[i]=='?': s[i] = 'a'
    res = ''
    for c in s: res+=c
    return res


s,t = input(), input()
lastMatch = getLastMatch(s,t)
if lastMatch == -1:
    print('UNRESTORABLE')
else:
    print(getS(s,t,lastMatch))
n = int(input())
ans = [0 for i in range (n)]
for i in range(n):
  a,b,c = map(int,input().split())
  if c % 2 == 1:
    if ans[a-1] == ans[b-1]:
      ans[b-1] == 1
for i in range(n):
  print(ans[i])
    

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n=int(input())
graph=[[] for i in range(n)]
color=[-1]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    graph[a-1].append([b-1,c%2])
    graph[b-1].append([a-1,c%2])
def coloring(pre,c):
  color[pre]=c
  for i,j in graph[pre]:
    if color[i]<0:
      coloring(i,color[pre]^j)
coloring(0,1)
for i in color:
  print(i)
a,b = map(int,input().split())
ans = 0
for i in range():
  if a*i <= b:
    ans += 1
  else:
    break
print(ans)

### FIXED CODE ###

x,y = map(int, input().split())
cnt = 1
while x*2 ** cnt <= y:
    cnt += 1
print(cnt)
#ABC060B
A, B, C = map(int, input().split()
if A % 2 == (2 * B + 1) % 2:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

#ABC060B
A, B, C = map(int, input().split())
ok = False
for i in range(1,B+1):
    if i*A % B ==C:
        ok = True
if ok:
    print("YES")
else:
    print("NO")
s = input()
print(s[:len(s)-8]

### FIXED CODE ###

s = input()
print(s[:(len(s)-8)])
l = raw_input().split()
if l[0]+l[1]==15:
    print('+')
elif l[0]*l[1] ==15:
    print('*')
else:
    print('x')

### FIXED CODE ###

l = input().split()
if int(l[0])+int(l[1])==15:
    print('+')
elif int(l[0])*int(l[1]) ==15:
    print('*')
else:
    print('x')
n , k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9 + 7
a.sort(reverse=True)
ans = 1
plus = []
minus = []
zero = 0
for i in range(n):
    if a[i] > 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus.append(a[i])
    elif a[i] == 0:
        zero += 1
if len(plus) + len(minus) < k:
    print(0)
elif len(minus) == 0:
    for i in range(k):
        ans *= plus[i]
        ans %= mod
    print(ans)
elif len(plus) == 0:
    if k % 2 == 0:
        for i in range(k):
            ans *= minus[n-1-i]
            ans %= mod
        print(ans)
    elif k % 2 == 1:
        if zero >= 1:
            print(0)
        elif zero == 0:
            for i in range(k):
                ans *= minus[i]
                ans %= mod
            print(ans)
else:
    rplus = [1]
    for i in range(len(plus)):
        rplus.append(rplus[-1] * plus[i])
    rminus = [1]
    for i in reversed(range(len(minus))):
        rminus.append(rminus[-1] * minus[i])
    for i in range(0,k+1,2):
        cou = 1
        if len(rminus) < i or len(rplus) < k - i:
            continue
        cou = rminus[i] * rplus[k-i]
        if cou > ans:
            ans = cou
    print(ans%mod)

### FIXED CODE ###

from collections import deque
n , k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9 + 7
ans = 1
plus = []
minus = []

if n == k:
    for i in range(n):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
    
for i in range(n):
    if a[i] >= 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus.append(a[i])

if not plus and k % 2 == 1:
    minus.sort(reverse=True)
    for i in range(k):
        ans *= minus[i]
        ans %= mod
    print(ans)
    exit()

plus.sort(reverse=True)
minus.sort()
plus = deque(plus)
minus = deque(minus)

cou = []
while True:
    if len(cou) == k:
        break
    elif len(cou) == k-1:
        cou.append(plus.popleft())
        break
    else:
        if len(plus)>=2 and len(minus)>=2:
            p1 = plus.popleft()
            p2 = plus.popleft()
            m1 = minus.popleft()
            m2 = minus.popleft()
            if p1*p2 > m1*m2:
                cou.append(p1)
                plus.appendleft(p2)
                minus.appendleft(m2)
                minus.appendleft(m1)
            else:
                cou.append(m1)
                cou.append(m2)
                plus.appendleft(p2)
                plus.appendleft(p1)
        elif len(plus) < 2:
            m1 = minus.popleft()
            m2 = minus.popleft()
            cou.append(m1)
            cou.append(m2)
        elif len(minus) < 2:
            p1 = plus.popleft()
            cou.append(p1)

        
for i in cou:
    ans *= i
    ans %= mod
print(ans)
n = input()
sum = 0

for i in range(0, n-1):
   x = input()
   m[i] = x
   sum = sum + m[i]

min = min(m[i] for i in range(0, n-1))
max = max(m[i] for i in range(0, n-1))

print '%d %d &d' &(min, max, sum)

### FIXED CODE ###

n = input()
m = map(int, raw_input().split())

print '%d %d %d' %(min(m), max(m), sum(m))
# (A,B,C)<=3500
# 4/N = (1/A)+(1/B)+(1/C)
# (4/N)-(1/A) = (1/B)+(1/C)
# (4A-N)/AN   = (B+C)/BC

# XX-(4A-N)X+AN=0
# X = (-b±sqrt(bb-4c))/2 (a=1)
#   = ((4A-N)±sqrt((4A-N)(4A-N)-4AN))/2
#   = ((4A-N)±sqrt(16AA-12AN+NN))/2


def BiSearch(Func,N):
    Left  = 0
    FLeft = Func(Left)
    Right  = N
    FRight = Func(Right)
    Flag = False
    while Left<=Right:
        Med  = (Left+Right)//2
        FMed = Func(Med)
        if FMed==N:
            Flag = True
            return Med
        elif FMed>N:
            Right  = Med-1
            FRight = Func(Right)
        else:
            Left  = Med+1
            FLeft = Func(Left)
    if not Flag:
        return False
def SquareRootSearch(K):
    return BiSearch(lambda N:N*N,K)

N = int(input())
for TA in range(1,3501):
    SqrtX = SquareRootSearch(16*(TA**2)-(12*TA*N)+(N**2))
    if SqrtX:
        NumerB = (4*TA-N)+SqrtX
        NumerC = (4*TA-N)-SqrtX
        if NumerB%2==0 and NumerC%2==0 and NumerB>0 and NumerC>0:
            A = TA
            B = NumerB//2
            C = NumerC//2
print('{} {} {}'.format(A,B,C))

### FIXED CODE ###

N = int(input())
A,B,C = 0,0,0
for TA in range(1,3501):
    for TB in range(1,3501):
        Numer = TA*TB*N
        Denom = 4*TA*TB-(TA+TB)*N
        if Denom>0 and Numer>0 and Numer%Denom==0:
            A = TA
            B = TB
            C = Numer//Denom
print('{} {} {}'.format(A,B,C))
n = list(map(int,input().split()))
word = [input() for i in range(n[1])]
print(''.join(sorted(word)))


### FIXED CODE ###

n = list(map(int,input().split()))
word = [input() for i in range(n[0])]
print(''.join(sorted(word)))
abc=[]
answer=0
for i in range(5):
    d=int(input())
    if d%10==0:
        answer+=d
    else:
        answer+=(int(d/10+1))*10
        abc.append(d%10)
answer-=10-min(abc)
print(answer)

### FIXED CODE ###

abc=[]
answer=0
for i in range(5):
    d=int(input())
    if d%10==0:
        answer+=d
    else:
        answer+=(int(d/10+1))*10
        abc.append(d%10)
if len(abc)>0:
    answer-=10-min(abc)
print(answer)
n = int(input())
nums = map(int, input().split())

start_num = 1
result_list = []
for num in nums:
    if num == start_num:
        result_list.append(num)
        start_num += 1

if len(result_list) == 0:
    print(-1)
else:
    print(n - len(result_list))

### FIXED CODE ###

#a,bの最小公倍数
a, b = list(map(int, input().split()))

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

def lcm(a, b):
    return a * b // gcd (a, b)

print(lcm(a, b))
N,Q=map(int,input().split())
side=[[0 for i in range(2)]for j in range(N-1)]
yobun=[[0 for i in range(2)]for j in range(Q)]

l=[0]*N
ll=[0 for i in range(N)] for j in range(N)

for i in range(N-1):
    side[i][0],side[i][1]=map(int,input().split())
    
def kyusyu(p,x):
    l[p-1]+=x
    for i in range(N-1):
        if p==side[i][0]:
            kyusyu(side[i][1],x)
    
for i in range(Q):
    yobun[i][0],yobun[i][1]=map(int,input().split())
    kyusyu(yobun[i][0],yobun[i][1])



            
#for i in range(Q):
#    kyusyu(yobun[i][0],yobun[i][1])
    
    
print(l)
    

### FIXED CODE ###

# coding: utf-8
# Your code here!
#パクリゆるして
#グラフのようななにか

import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000)

from collections import deque


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

tree=[[]*(N+1) for i in range(N+1)]
point=[0]*(N+1)

for _ in range(N-1):
    a,b=map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
    
for _ in range(Q):
    p,x=map(int,input().split())
    point[p]+=x
#print(point)

d=deque([[1,0]])

while d:
    node,parent=d.popleft()
    point[node]+=point[parent]
    lis=tree[node]
    for child in lis:
        if child==parent:
            continue
        d.append([child,node])
    #print(d)

print(*point[1:])
h = int(input(""))
w = int(input(""))
if h*w % 2 == 0:
    print(h*w/2)
else:
    print((h*w+1)/2)

### FIXED CODE ###

H, W = list(map(int, input().split()))
if H==1 or W==1:
    print(1)
    exit()
res = int((H+1)/2) * W
if H%2==1:
    res -= int(W/2)
print(res)
n = int(input()) 
l = list(map(int, input().split()))
if l[0] != 0:
    print(0)
    exit()

max_vertex = max(l)
ll = []
l=sorted(l)
l.append('end')
c=1
for i in range(1, n):
    if l[i] != l[i+1]:
        if c == 0:
            print(0)
            exit();
        ll.append(c)
        c = 0
    c+=1
   
count = 1
for i in range(1, max_vertex):
    tmp = ll[i-1]
    count *= pow(tmp, ll[i])
print(count%998244353)

### FIXED CODE ###

n = int(input()) 
l = list(map(int, input().split()))
if l[0] != 0:
    print(0)
    exit()

for i in range(1, n):
    if l[i] == 0:
        print(0)
        exit()

max_vertex = max(l)
ll = []
l=sorted(l)
l.append(-4)
c=1
for i in range(1, n):
    if l[i] != l[i+1]:
        if l[i] != l[i+1]-1 and l[i+1] > 0:
            print(0)
            exit()
        ll.append(c)
        c = 0
    c+=1

count = 1
for i in range(1, max_vertex):
    tmp = ll[i-1]
    count *= pow(tmp, ll[i])
print(count%998244353)
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

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


def ok(X):
    cnt = 0
    for a in A:
        cnt += (a - 1) // X

    return cnt <= K


def solve():
    l, r = -1, 1000000000

    while l + 1 < r:
        c = (l + r) // 2
        if ok(c):
            r = c
        else:
            l = c

    return r

print(solve())

### FIXED CODE ###

import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

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


def ok(X):
    cnt = 0
    for a in A:
        cnt += (a - 1) // X

    return cnt <= K


def solve():
    l, r = 0, 1000000000

    while l + 1 < r:
        c = (l + r) // 2
        if ok(c):
            r = c
        else:
            l = c

    return r


print(solve())
N, K, *PC = map(int, open(0).read().split())
P, C = [0] + PC[:N], [0] + PC[N:]

ans = float("-inf")
for start in range(1, N + 1):
    acc = 0
    cur = start
    cycle = 0
    for l in range(K):
        cur = P[cur]
        acc += C[cur]
        ans = max(ans, acc)
        if cur == start:
            cycle = l + 1
            break

    q, r = divmod(K, cycle)
    if r == 0 and q > 1:
        r = cycle
        q -= 1

    res = acc * q
    ans = max(ans, res)
    for l in range(r):
        cur = P[cur]
        res += C[cur]
        ans = max(ans, res)

print(ans)

### FIXED CODE ###

from itertools import accumulate

N, K, *PC = map(int, open(0).read().split())
P, C = [0] + PC[:N], [0] + PC[N:]

ans = float("-inf")
for start in range(1, N + 1):
    path = []

    cur = P[start]
    path = [C[start]]
    while cur != start:
        path.append(C[cur])
        cur = P[cur]

    A = list(accumulate(path))
    q, r = divmod(K, len(path))
    res = 0
    if A[-1] >= 0:
        if r == 0:
            q -= 1
            r += len(path)
        res += A[-1] * q
    elif q >= 1:
        r = len(path)

    ans = max(ans, res + max(A[:r]))

print(ans)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    long N, A, B;
    cin >> N >> A >> B;
    vector<long> h;
    for (int i=0; i<N; i++){
        long input;
        cin >> input;
        h.push_back(input);
    }

    
    long ans = 0;
    vector<long> temp;
    while (h.size() != 0){
        bool first = true;
        make_heap(h.begin(),h.end());
        for (auto x : h){
            if (first) {x -= A; first = false;}
            else{ x -= B;}
            if (x > 0) temp.push_back(x);
        }
        h.clear();
        for (auto x : temp) h.push_back(x);
        temp.clear();
        ans++;
    }
    cout << ans << endl;
    return 0;
}

### FIXED CODE ###

with open(0) as f:
    N, A, B, *H = map(int, f.read().split())

diff = A - B #追加ダメージ
T = (max(H)+B-1)//B #答えはT以下

def clearable(t): #t回以内で敵を全滅できるか判定
    Higher = [h-B*t for h in H if h-B*t > 0]
    return True if sum([(h+diff-1)//diff for h in Higher]) <= t else False

def binary_search(a, b, judge): #b must be a or higher
    if a == b:
        return a, b
    
    c = a + (b - a)// 2
    return (a, c) if judge(c) else (c+1, b)

a, b = 0, T
while a != b:
    a, b = binary_search(a, b, clearable)
print(a)
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(M)]
AB.reverse()
par=list(range(1,N+1))
size=[1]*N

ans=[(N-1)*N//2]*M

def spar(n):
  if par[n-1]==n:
    return n
  else:
    return spar(par[n-1])

for i in range(0,M-1):
  A,B=AB[i]
  pa,pb=spar(par[A-1]),spar(par[B-1])
  if pa==pb:
    ans[i+1]=ans[i]
  else:
    ans[i+1]=ans[i]-size[pa-1]*size[pb-1]
    sa,sb=size[pa-1],size[pb-1]
    size[pa-1]+=sb
    size[pb-1]+=sa
  par[pa-1]=pa
  par[pb-1]=pa
  
for i in reversed(ans):
  print(i)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(M)]
AB.reverse()
par=list(range(1,N+1))
size=[1]*N

ans=[(N-1)*N//2]*M

def spar(n):
  if par[n-1]==n:
    return n
  else:
    par[n-1]=spar(par[n-1])
    return par[n-1]

for i in range(0,M-1):
  A,B=AB[i]
  pa,pb=spar(par[A-1]),spar(par[B-1])
  if pa==pb:
    ans[i+1]=ans[i]
  else:
    ans[i+1]=ans[i]-size[pa-1]*size[pb-1]
    sa,sb=size[pa-1],size[pb-1]
    size[pa-1]+=sb
    size[pb-1]+=sa
  par[pa-1]=pa
  par[pb-1]=pa
  
for i in reversed(ans):
  print(i)
from fractions import gcd
from functools import reduce

N, M = map(int, input().split())
alist = list(map(lambda k: int(k) // 2, input().split()))

numdic = {}

def lcm(x, y):
    return (x * y) // gcd(x,y)

def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

lcmnum = lcm_list(alist)

for i in alist:
    if (lcmnum//i)%2==0:
        print(0)
        sys.exit()

pmax = M // lcmnum
pmax = pmax - 1 if pmax % 2 == 0 else pmax

print((pmax+1)//2)


### FIXED CODE ###

from fractions import gcd
from functools import reduce
import sys

N, M = map(int, input().split())
alist = list(map(lambda k: int(k) // 2, input().split()))

numdic = {}

def lcm(x, y):
    return (x * y) // gcd(x,y)

def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

lcmnum = lcm_list(alist)

for i in alist:
    if (lcmnum//i)%2==0:
        print(0)
        sys.exit()

pmax = M // lcmnum
pmax = pmax - 1 if pmax % 2 == 0 else pmax

print((pmax+1)//2)
import sys
import math

str = sys.stdin.readline()

a = int(str.split()[0])
b = int(str.split()[1])

print(int(a * b / math.gcd(a,b)))


### FIXED CODE ###

import sys
import fractions

str = sys.stdin.readline()

a = int(str.split()[0])
b = int(str.split()[1])

print((a * b) // fractions.gcd(a,b))