Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


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

if N == 1:
    print(M)
    exit()

if is_prime(M):
    print(1)
    exit()

ans = 0
for i in range(1, M+1):
    d, m = divmod(M, i)
    if m == 0 and d >= N:
        ans = i
    if d < N:
        break

print(ans)



### FIXED CODE ###

def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ass.append(i)
            ass.append(n//i)
    return ass


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

K = divisor(M)

ans = 0
for k in K:
    if N * k <= M:
        ans = max(ans, k)


print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
c = 0
for i in range(q):
    qy = list(input().split())
    if qy[0] == "1":
        c += 1
    else:
        if qy[1] == "1" and c % 2 == 0:
            s = qy[2] + s
        elif qy[1] == "1" and c % 2 == 1:
            s = s + qy[2]
        elif qy[1] == "2" and c % 2 == 0:
            s = s + qy[2]
        else:
            s = qy[2] + s
if c % 2 == 0:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

s = input()
q = int(input())
c = 0
t = ""
u = ""
for i in range(q):
    qy = list(input().split())
    if qy[0] == "1":
        c += 1
    else:
        if (qy[1] == "1" and c % 2 == 0) or (qy[1] == "2" and c % 2 == 1):
            t = qy[2] + t
        else:
            u = u + qy[2]
ans = t + s + u
if c % 2 == 0:
    print(t + s + u)
else:
    print(ans[::-1])
### BUGGY CODE ###

N,K = map(int,input().split())
h_s = list(map(int,input().split()))
INF = 10000000000
dp = [INF]*N
dp[0] = 0
K = min(K,N-1)
for i in range(1,N):
    for j_j in range(min(K,i)):
        j = j_j + 1
        dp[i] = min((dp[i-j] + abs(h_s[i] - h_s[i-j])),dp[i])
print(dp[-1])


### FIXED CODE ###

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

dp = [1e9]*N
dp[0] = 0
for i, b in enumerate(H):
  if i != 0:
    x = max(0, i-K)
    dp[i] = min([abs(b-d)+p for d, p in zip(H[x:i], dp[x:i])])
print(dp[-1])
### BUGGY CODE ###

class BIT:
    def __init__(self, n, MOD):
        self.n = n
        self.data = [0] * (n + 1)
        self.MOD = MOD

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            s %= self.MOD
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            self.data[i] %= self.MOD
            i += i & -i


n, k = map(int, input().split())
mod = 998244353
bit = BIT(n + 2, mod)
ranges = []
for _ in range(k):
    l, r = map(int, input().split())
    ranges.append((l, r))

bit.add(1, 1)

for i in range(1, n):
    v = bit.sum(i)
    for l, r in ranges:
        bit.add(i + l, v)
        bit.add(min(n + 1, i + r + 1), -v)
print(bit.sum(n) - bit.sum(n - 1) % mod)


### FIXED CODE ###

class BIT:
    def __init__(self, n, MOD):
        self.n = n
        self.data = [0] * (n + 1)
        self.MOD = MOD

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            s %= self.MOD
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            self.data[i] %= self.MOD
            i += i & -i


n, k = map(int, input().split())
mod = 998244353
bit = BIT(n + 2, mod)
ranges = []
for _ in range(k):
    l, r = map(int, input().split())
    ranges.append((l, r))

bit.add(1, 1)

for i in range(1, n):
    v = bit.sum(i)
    for l, r in ranges:
        bit.add(i + l, v)
        bit.add(min(n + 1, i + r + 1), -v)
print((bit.sum(n) - bit.sum(n - 1)) % mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from math import gcd
from functools import reduce
from collections import Counter
import heapq


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def sieve(n):
    """
    n以下の素数を昇順に列挙する
    """
    prime_divisors = [1 for i in range(n+1)]
    for i in range(2, n+1):
        if prime_divisors[i] == 1:
            for j in range(i, n+1, i):
                prime_divisors[j] = i
    return prime_divisors


def solve(N, A):
    prime_divisors = sieve(max(A))
    c = Counter()
    for a in A:
        p = a
        d = Counter()
        while p > 1:
            q = prime_divisors[p]
            d[q] = 1
            p //= q
        c += d
    if len(c) == 0 or c.most_common()[0][1] == 1:
        return "pairwise coprime"
    if reduce(gcd, A) == 1:
        return "setwise coprime"
    return "not coprime"


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


### FIXED CODE ###

import sys
input = sys.stdin.readline
from math import gcd
from functools import reduce
from collections import defaultdict


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def is_pairwise_coprime(A):
    n = max(A)
    base = [False for i in range(n+1)]
    for a in A:
        if a > 1 and base[a]:
            return False
        base[a] = True
    
    is_prime = [True for i in range(n+1)]
    for i in range(2, n+1):
        if is_prime[i]:
            include_number = set()
            if base[i]:
                include_number.add(i)
            for j in range(i+i, n+1, i):
                is_prime[j] = False
                if base[j]:
                    include_number.add(j)
            if len(include_number) >= 2:
                return False
    return True


def solve(N, A):
    if is_pairwise_coprime(A):
        return "pairwise coprime"
    if reduce(gcd, A) == 1:
        return "setwise coprime"
    return "not coprime"


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
### BUGGY CODE ###

from decimal import *
getcontext().prec = 100000000
a,b,c=map(int,input().split())
if Decimal(a).sqrt()+Decimal(b).sqrt()<Decimal(c).sqrt():
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import math
a,b,c=map(int,input().split())
if 4*a*b<(c-a-b)*(c-a-b) and c>a+b:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

I=lambda:map(int,input().split())
n,q=I()
s=[0]
d=s*n
e=[[]for _ in d]
while~-n:n-=1;a,b=I();e[a-1]+=b-1,;e[b-1]+=a-1,
while q:q-=1;p,x=I();d[p-1]-=x
d[0]*=-1
while s:
 v=s.pop()
 for w in e[v]:
  if d[w]<w:d[w]=d[v]-d[w];s+=w,
print(*d)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def dfs(v):
    for w in e[v]:
        if root[w]>=0:continue
        root[w]=v
        dfs(w)
def dfs2(v):
    for w in e[v]:
        if f[w]:continue
        f[w]=1
        data[w]+=data[v]
        dfs2(w)
input=sys.stdin.readline
n,q=map(int,input().split())
e=[[]for _ in range(n)]
root=[0]+[-1]*(n-1)
data=[0]*n
for _ in range(n-1):
    a,b=map(int,input().split())
    e[a-1]+=b-1,
    e[b-1]+=a-1,
#dfs(0)
for _ in range(q):
    p,x=map(int,input().split())
    data[p-1]+=x
f=[1]+[0]*(n-1)
dfs2(0)
print(*data)
### BUGGY CODE ###

N=int(input())
Ans=1
for i in range(1,N+1):
  Ans*=i
print(Ans%(10**9+7))

### FIXED CODE ###

N=int(input())
Ans=1
for i in range(1,N+1):
  Ans*=i
  Ans%=(10**9+7)

print(Ans)
### BUGGY CODE ###

from fractions import gcd

n = int(input())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
lcm = aaa[0]
for a in aaa[1:]:
    lcm = lcm * a // gcd(lcm, a)

ans = 0
for a in aaa:
    ans = (ans + lcm // a) % MOD
print(ans)


### FIXED CODE ###

def prime_factorize(n):
    i = 2
    res = {}
    while i * i <= n:
        if n % i != 0:
            i += 1
            continue
        res[i] = 0
        while n % i == 0:
            res[i] += 1
            n //= i
        i += 1
    if n != 1:
        res[n] = 1
    return res


n = int(input())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
lcm_ppf = prime_factorize(aaa[0])
for a in aaa[1:]:
    for p, c in prime_factorize(a).items():
        if p in lcm_ppf:
            lcm_ppf[p] = max(lcm_ppf[p], c)
        else:
            lcm_ppf[p] = c

lcm = 1
for p, c in lcm_ppf.items():
    lcm = lcm * pow(p, c, MOD) % MOD
# print(lcm)

ans = 0
for a in aaa:
    ra = pow(a, MOD - 2, MOD)
    ans = (ans + lcm * ra) % MOD
print(ans)
### BUGGY CODE ###

import numpy as np
p = 10**9+7
def pow(X,k):
    if k==0:
        return np.eye(X.shape[0])
    if k==1:
        return X
    if k%2==0:
        return np.dot(pow(X,k//2),pow(X,k//2))%p
    else:
        return np.dot(X,np.dot(pow(X,(k-1)//2),pow(X,(k-1)//2))%p)%p
N,K = map(int,input().split())
A = np.zeros((N,N))
for i in range(N):
    a = np.array(list(map(int,input().split())))
    A[i][:] = a[:]
X = pow(A,K)
cnt = 0
for i in range(N):
    for j in range(N):
        cnt = (cnt+X[i][j])%p
print(int(cnt))

### FIXED CODE ###

p = 10**9+7
def pow(X,k):
    if k==0:
        return [[1 if i==j else 0 for j in range(N)] for i in range(N)]
    if k==1:
        return X
    if k%2==0:
        Y = pow(X,k//2)
        Z = [[0 for _ in range(N)] for _ in range(N)]
        for i in range(N):
            for j in range(N):
                for m in range(N):
                    Z[i][j] = (Z[i][j]+Y[i][m]*Y[m][j])%p
        return Z
    else:
        Y = pow(X,(k-1)//2)
        Z = [[0 for _ in range(N)] for _ in range(N)]
        for i in range(N):
            for j in range(N):
                for m in range(N):
                    Z[i][j] = (Z[i][j]+Y[i][m]*Y[m][j])%p
        Z1 = [[0 for _ in range(N)] for _ in range(N)]
        for i in range(N):
            for j in range(N):
                for m in range(N):
                    Z1[i][j] = (Z1[i][j]+Z[i][m]*X[m][j])%p
        return Z1
N,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
X = pow(A,K)
cnt = 0
for i in range(N):
    for j in range(N):
        cnt = (cnt+X[i][j])%p
print(int(cnt))
### BUGGY CODE ###

inf = 10**10
H, N = map(int, input().split())
A = []
B = []
for n in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
dp = [[0 for h in range(H+1)] for n in range(N+1)]
# dp[n][h]は0~n-1の魔法で体力hを削るのに使う魔力
dp[0] = [0] + [inf for h in range(1, H+1)]
for n in range(1, N+1):
    for h in range(H+1):
        dp[n][h] = min(dp[n - 1][h], dp[n][max(0, h - A[n - 1])] + B[n - 1])
print(dp[N][H])


### FIXED CODE ###

inf = 10 ** 9


def main():
    H, N = map(int, input().split())
    AB = []
    for n in range(N):
        a, b = map(int, input().split())
        AB.append((a, b))
    AB.sort(reverse=True, key=lambda x: x[0])
    dp = [inf] * (H + 10 ** 4)
    dp[0] = 0
    for a, b in AB:
        for h in range(H):
            # if dp[h] == inf:
            #     continue
            # else:
            #     dp[h+a] = min(dp[h]+b, dp[h+a])
            if dp[h] != inf:
                tmp = dp[h] + b
                if tmp < dp[h + a]:
                    dp[h + a] = tmp
    print(min(dp[H:]))


main()
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

kukan = 0
kukan_list = []
for i in range(n - k + 1):
    if kukan < sum(p[i:i + k]):
        kukan = sum(p[i:i + k])
        kukan_list = p[i:i + k]

ans = 0
for i in range(k):
    if kukan_list[i] % 2 == 0:
        x = kukan_list[i] / 2 + 0.5
    else:
        x = kukan_list[i] // 2 + 1
    ans += x
print(ans)


### FIXED CODE ###

from collections import deque
import itertools
import time

n, k = map(int, input().split())
p = list(map(int, input().split()))

kukan = 0
for i in range(k):
    kukan += p[i]

kukan_max = kukan
for i in range(n - k + 1):
    kukan_max = max(kukan_max, kukan)
    if i+k<n:
        kukan += p[i+k]
        kukan -= p[i]
ans = kukan_max / 2 + 0.5 * k
print(ans)
### BUGGY CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=tf-8
#

"""
"""

from collections import defaultdict
import bisect
from itertools import product
from collections import deque

import sys
input = sys.stdin.readline

def solve(h,w,ch,cw,dh,dw,s):
    d = [[10**7]*w for _ in range(h)]
    d[ch][cw] = 0
    dis0 = [(1,0),(0,1),(-1,0),(0,-1)]
    dis1 = [(i,j) for i,j in product(range(-2,3),range(-2,3)) if 1 < abs(i)+abs(j)]
    Q = deque([(ch,cw)])
    ans = -1
    while Q:
        pos1 = Q.pop()
        i, j = pos1
        alt = d[i][j] 
        if i == dh and j==dw:
            ans = d[dh][dw]
            break
        for k,l in [(i+a,j+b) for a,b in dis0 if 0 <= i+a < h and 0 <= j+b <w and s[i+a][j+b]=="." and d[i+a][j+b] > alt]:
            d[k][l] = alt
            Q.append((k,l))
        alt += 1
        for k,l in [(i+a,j+b) for a,b in dis1 if 0 <= i+a < h and 0 <= j+b <w and s[i+a][j+b]=="." and d[i+a][j+b] > alt]:
            d[k][l] = alt
            Q.appendleft((k,l))
    print(ans)



def main():
    h, w = list(map(int,input().split()))
    ch, cw = list(map(int,input().split()))
    dh, dw = list(map(int,input().split()))
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1
    s = []
    for _ in range(h):
        s.append(list(input().rstrip()))
    solve(h,w,ch,cw,dh,dw,s)


if __name__ == "__main__":
    main()

### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=tf-8
#

"""
"""

from collections import defaultdict
import bisect
from itertools import product
from collections import deque

import sys
input = sys.stdin.readline

def solve(h,w,ch,cw,dh,dw,s):
    d = [[10**7]*w for _ in range(h)]
    d[ch][cw] = 0
    dis0 = [(1,0),(0,1),(-1,0),(0,-1)]
    dis1 = [(i,j) for i,j in product(range(-2,3),range(-2,3)) if 1 < abs(i)+abs(j)]
    Q = deque([(ch,cw)])
    ans = -1
    while Q:
        pos1 = Q.pop()
        i, j = pos1
        if i == dh and j==dw:
            ans = d[dh][dw]
            break
        for pos2 in [(i+a,j+b) for a,b in dis0 if 0 <= i+a < h and 0 <= j+b <w and s[i+a][j+b]=="."]:
            k, l = pos2
            alt = d[i][j] 
            if d[k][l] > alt:
                d[k][l] = alt
                Q.append((k,l))
        for pos2 in [(i+a,j+b) for a,b in dis1 if 0 <= i+a < h and 0 <= j+b <w and s[i+a][j+b]=="."]:
            k, l = pos2
            alt = d[i][j]+1
            if d[k][l] > alt:
                d[k][l] = alt
                Q.appendleft((k,l))
    print(ans)



def main():
    h, w = list(map(int,input().split()))
    ch, cw = list(map(int,input().split()))
    dh, dw = list(map(int,input().split()))
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1
    s = []
    for _ in range(h):
        s.append(list(input().rstrip()))
    solve(h,w,ch,cw,dh,dw,s)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

from math import sqrt,floor
from sys import stdin

def cntPrime(n):
    mx = sqrt(n)
    if n % 2 == 0:
      l = [0, 1] + [1, 0] * (int(n/2) - 1)
    else:
      l = [0, 1] + [1, 0] * (int(n/2) - 1) + [1]
    c = 3
    while c < mx:
        for k in range(c*2, n+1, c):
            l[k-1] = 0
        c = l[(c+1):].index(1) + c +2
        while c % 2 == 0:
            c = l[(c+1):].index(1) + c +2
    return sum(l)
for n in stdin:
    n = int(n)
    print(cntPrime(n))

### FIXED CODE ###

from math import sqrt,floor
from sys import stdin

def cntPrime(n):
    mx = sqrt(n)
    if n % 2 == 0:
      l = [0, 1] + [1, 0] * (int(n/2) - 1)
    else:
      l = [0, 1] + [1, 0] * (int(n/2) - 1) + [1]
    c = 3
    while c < mx:
        for k in range(c*2, n+1, c):
            l[k-1] = 0
        c = l[(c+1):].index(1) + c +2
        while c % 2 == 0:
            c = l[(c+1):].index(1) + c +2
    return l
t = cntPrime(1000000)
for n in stdin:
    n = int(n)
    print(sum(t[:n]))
### BUGGY CODE ###

N = int(input())

isok=False
for h in range(1,3501):
    for n in range(1,3501):
        bunsi = 4*h*n - N*(h+n)
        bunbo = N*h*n
        if bunsi>0 and bunbo%bunsi==0:
            w = bunbo//bunsi
            isok = True
            break
    if isok:break
        
if isok:
    print(h,n,w)
else:
    print("ここ来たらマジでヤバいが")

### FIXED CODE ###

#%%time
N = int(input())

isok=False
for h in range(1,3501):
    bunsi = 4*h - N
    bunbo = N*h
    if bunsi>0:
        n = (bunbo//bunsi) + 1
        bunsi = 4*h*n - N*(h+n)
        bunbo = N*h*n
        if bunsi>0 and bunbo%bunsi==0:
            w = bunbo//bunsi
            isok = True
            break
        
if isok:
    print(h,n,w)
else:
    print("ここ来たらマジでヤバいが")
### BUGGY CODE ###

k = int(input())

check = False
if k%2 == 0:
  check = True
  
if check == False:
  check_s = "7"
  while(True):
    if int(check_s)%k == 0:
      break
    check_s += "7"
  print(len(check_s))
else :
  print(-1)

### FIXED CODE ###

k = int(input())

answer = -1
x = 7
for index in range(k) :
  if x % k == 0:
    answer = index + 1
    break
  x = (10 * x + 7) % k
  
print(answer)
### BUGGY CODE ###

def main():
    n = int(input())
    a = list( map( int, input().split()))
    sum = 1
    for i in a:
        sum *= i
    if sum >1000000000000000000:
        print(-1)
    else:
       print(sum)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import copy

def main():
    n = int(input())
    a = list( map( int, input().split()))
    sum = 1
    if 0 in a:
        print(0)
    else:
        for i in a:
            sum = sum * i
            if sum > 1000000000000000000:
                print(-1)
                exit()
        print(sum)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

INF = 10**9

N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(M)]
W = [[INF for _ in range(N+1)] for __ in range(N+1)]

for i in range(1, N+1):
     W[i][i] = 0

for x in X:
     A, B, C = x
     W[A][B] = C
     W[B][A] = C

for k in range(1, N+1):
     for j in range(1, N+1):
         for i in range(j, N+1):
             W[i][j] = min(W[i][j], W[i][k]+W[k][j])
             W[j][i] = W[i][j]

from itertools import permutations

ans = INF
for r_ in permutations(r):
    count = 0
    for i in range(R-1):
        count += W[r_[i]][r_[i+1]]
    ans = min(ans, count)
print(ans)

### FIXED CODE ###

INF = 10**9

N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))
W = [[INF for _ in range(N+1)] for __ in range(N+1)]
for i in range(1, N+1):
    W[i][i] = 0

for _ in range(M):
    A, B, C = list(map(int, input().split()))
    W[A][B] = C
    W[B][A] = C

import heapq

for i in range(1, N+1):
    heap = []
    checked = [False for _ in range(N+1)]
    for j in range(1, i+1):
        heapq.heappush(heap, (W[i][j], j))
    while len(heap) > 0:
        wij, j = heapq.heappop(heap)
        if checked[j]:
            continue
        for k in range(i+1, N+1):
            wik = wij + W[j][k]
            if wik <= W[i][k]:
                W[i][k] = wik
                W[k][i] = wik
                heapq.heappush(heap, (wik, k))
        checked[j] = True

from itertools import permutations

ans = INF
for r_ in permutations(r):
    count = 0
    for i in range(R-1):
        x = W[r_[i]][r_[i+1]]
        if x >= INF:
            break
        count += x
        if count >= ans:
            break
    else:
        ans = count
print(ans)
### BUGGY CODE ###

N = int(input())
h = list(map(int , input().split()))
dp = [[0]*10000 for i in range(N)]
import sys
sys.setrecursionlimit(100000)
def dfs(i,c):
    if i == N:
        return 10000
    if dp[i][c] >0:
        return dp[i][c]
    else:
        if i == N-1:
            return abs(h[i] - c)
        dp[i][c] = min(dfs(i+1, h[i])+abs(h[i]-c),dfs(i+2, h[i])+abs(h[i]-c))
        return dp[i][c]
print(dfs(0,h[0]))


### FIXED CODE ###

N = int(input())
h = list(map(int , input().split()))
dp = [10**9+1]*N
dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2,N):
    dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))
print(dp[N-1])
### BUGGY CODE ###

def solve(lr,N,Q,S):
    answer = []
    for i in range(Q):
        answer.append(S[int(lr[i][0])-1:int(lr[i][1])].count('AC'))
    for i in range(Q):
        print(answer[i])

 
def main():
    N,Q= map(int,input().split())
    S = input()
    lr = [0]*Q
    for i in range(Q):
        lr[i]=input().rstrip().split()
    # S = 'ACACTACG'
    # N = 8
    # Q = 3
    # lr = [['3', '7'], ['2', '3'], ['1', '8']]
    solve(lr,N,Q,S)
 
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

def solve(lr,N,Q,S):
    #ACの総数をindex0~N-1まで全てだす
    count = [0]*N
    sum = 0
    for i in range(1,N):
       
        if S[i-1]=='A' and S[i]=='C':
            sum += 1
            count[i] = sum
        else:
            count[i] = sum

    # print(count)
    
    for i in range(Q):
        # print(int(lr[i][1]),int(lr[i][0]))
        print(count[int(lr[i][1])-1]-count[int(lr[i][0])-1])
    #     # print(S[int(lr[i][0])-1:int(lr[i][1])].count('AC'))



 
def main():
    N,Q= map(int,input().split())
    S = input()
    lr = [0]*Q
    for i in range(Q):
        lr[i]=input().rstrip().split()
    # S = 'ACACTACG'
    # N = 8
    # Q = 3
    # lr = [['3', '7'], ['2', '3'], ['1', '8']]
    solve(lr,N,Q,S)
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())

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

# rank保持のためにunionでrankを足し合わせる
# 島を数えるためにデフォルトのrank=1とする
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [1 for i in range(n)]

    def root(self, x):
        if (self.par[x]==x):
            return x
        else:
            # path compression
            self.par[x] = self.root(self.par[x])
            return self.root(self.par[x])

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if (x==y):
            return

        if (self.rank[x] < self.rank[y]):
            self.par[x] = y
            self.rank[y] += self.rank[x]
            self.rank[x] = 0
        else:
            self.par[y] = x
            self.rank[x] += self.rank[y]
            self.rank[y] = 0

    def find(self, x, y):
        return self.root(x)==self.root(y)
    
    def get_inconvenience(self):
        rankMat = np.zeros((len(self.rank), len(self.rank)))        
        for i in range(len(self.rank)):
            rankMat[i] = self.rank
            rankMat[i][i] = 0
        rank = np.array(self.rank)
        return int(np.sum(np.dot(rank, rankMat))/2)
    
    def get_inconvenience2(self):
        inconvenience = 0
        for i in range(len(self.rank)-1):
            inconvenience += self.rank[i] * sum(self.rank[i+1:])
        return inconvenience

uf = UnionFind(N)
inconvenience = []
for m in range(M):
    inconvenience.append(uf.get_inconvenience2())
    uf.union(pairs[m][0]-1, pairs[m][1]-1)

inconvenience = inconvenience[::-1]
for m in range(M):
    print(inconvenience[m])


### FIXED CODE ###

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

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

# rank保持のためにunionでrankを足し合わせる
# 島を数えるためにデフォルトのrank=1とする
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [1 for i in range(n)]

    def root(self, x):
        if (self.par[x]==x):
            return x
        else:
            # path compression
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if (x==y):
            return

        if (self.rank[x] < self.rank[y]):
            self.par[x] = y
            self.rank[y] += self.rank[x]
            self.rank[x] = 0
        else:
            self.par[y] = x
            self.rank[x] += self.rank[y]
            self.rank[y] = 0

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

        if x==y:
            return 0
        else:
            return self.rank[x] * self.rank[y]

uf = UnionFind(N)
inconvenience = [int(N*(N-1)/2)]
for m in range(M-1):
    inconvenience.append(inconvenience[-1] - uf.get_inconvenience(pairs[m][0]-1, pairs[m][1]-1))
    uf.union(pairs[m][0]-1, pairs[m][1]-1)

print(*inconvenience[::-1], sep='\n')