Harryxun/stf_run huggingface dataset:
h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]

def calc(s):
    res = []
    for v in s:
        v.append('-')
        tmp = []
        nc = ''
        nn = 0
        for c in v:
            if nc == '':
                nc = c
                nn += 1
                continue
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp = tmp + [0 for _ in range(nn)]
                else:
                    tmp = tmp + [nn for _ in range(nn)]
                nc = c
                nn = 1
        res.append(tmp)
    return res

def calc2(s):
    res = []
    for j in range(w):
        v = ['-']
        tmp = []
        nc = ''
        nn = 0
        for i in range(h+1):
            if i == h:
                c = '-'
            else:
                c = s[i][j]
            if nc == '':
                nc = c
                nn += 1
                continue
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp = tmp + [0 for _ in range(nn)]
                else:
                    tmp = tmp + [nn for _ in range(nn)]
                    nc = c
                    nn = 1
        res.append(tmp)
    return res

tate = calc2(S)
yoko = calc(S)
print(max([tate[j][i] + yoko[i][j] for i in range(h) for j in range(w) if tate[j][i] * yoko[i][j] != 0]) - 1)


### FIXED CODE ###

h, w = map(int, input().split())
S = [input() for _ in range(h)]

def calc(s):
    res = []
    for v in s:
        v = v + '-'
        tmp = []
        nc = v[0]
        nn = 0
        for c in v:
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        res.append(tmp)
    return res

def calc2(s):
    res = []
    for j in range(w):
        tmp = []
        nc = s[0][j]
        nn = 0
        for i in range(h):
            c = s[i][j]
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        if nc == '#':
            tmp.extend([0 for _ in range(nn)])
        else:
            tmp.extend( [nn for _ in range(nn)])
        res.append(tmp)
    return res

tate = calc2(S)
yoko = calc(S)

print(max([tate[j][i] + yoko[i][j] for i in range(h) for j in range(w) if tate[j][i] * yoko[i][j] != 0]) - 1)
l,m,n = map(int, input().split())
newlist = sorted([l,m,n])
if newlist(1)==5 & newlist(2)==5 & newlist(3)==7:
    print(str(YES))
else print(str(NO))

### FIXED CODE ###

l,m,n = map(int, input().split())
newlist = sorted([l,m,n])
if newlist[0]==5 and newlist[1]==5 and newlist[2]==7:
    print('YES')
else:
    print('NO')
N,K=(int(x) for x in input().split())
S=list(int(i) for i in input())
S[K] = S[K].lower()
print(','.join(S))

### FIXED CODE ###

N,K=(int(x) for x in input().split())
S=list(input())
S[K-1] = S[K-1].lower()
print(''.join(S))
import math

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

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

llcm=1
for i in range(n):
    llcm= lcm(llcm,l[i])

### FIXED CODE ###

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

cnt=0
f=0
for i in l:
    f += i-1
print(f)
n, k, q = map(int, input().split())
a = [int(input()) for i in range(q)]
import numpy as np

all_score = np.array([k for _ in range(n)])
for i in a:
    all_score -= 1
    all_score[i - 1] += 1

print(np.where(all_score > 0)[0].tolist()[0])

### FIXED CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for i in range(q)]

all_score = [k - q for _ in range(n)]
for ai in a:
    all_score[ai - 1] += 1
for j in all_score:
    if j > 0:
        print('Yes')
    else:
        print('No')
n = map(int, raw_input().split());

print(2*(n[0]+n[1]));
print(n[0] * n[1]);

### FIXED CODE ###

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

print a*b, 2*(a+b)
import sys

if __name__ == '__manin__':
  
    input=sys.argv[1]
    
    area = input^2 * 3.14
    base_area = 1^1 * 3.14 
    
    print int(area/base_areaa)

### FIXED CODE ###

if __name__ == '__main__':
   r = int(input())
   print(pow(r,2))
inf = float("inf")
dp = [inf]*N
dp[0] = 0 #initial situation

for i in range(1,N):
	for k in range(K):
		if i-1-k >= 0:
			dp[i] = min(dp[i],dp[i-1-k] + abs(h[i]-h[i-1-k]))
			
print(dp[N-1])

### FIXED CODE ###

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

inf = float("inf")
dp = [inf]*N
dp[0] = 0 #initial situation

for i in range(1,N):
	for k in range(K):
		if i-1-k >= 0:
			dp[i] = min(dp[i],dp[i-1-k] + abs(h[i]-h[i-1-k]))
			
print(dp[N-1])
a, b=map(int, input().split())
print(max(a+b,a-b,a*b)

### FIXED CODE ###

a, b=map(int, input().split())
print(max(a+b,a-b,a*b))
def main():
    N = int(input())
    A = list(map(int, input().split()))

    A.sort()
    A.reverse()

    i = 1
    j = 1
    while j < N:
        if A[j - 1] / 2 <= sum(A[j:]):
            i += 1
        else:
            break
        j += 1
    print(str(i))

main()

### FIXED CODE ###

def main():
    N, C, K = map(int, input().split())
    i = 0
    T = []
    while i < N:
        T.append(int(input()))
        i += 1
    T.sort()
    T.reverse()

    c = 1
    i = 1
    bus = 1
    time = T[0]
    while i < N:
        if time - T[i] > K or c == C:
            bus += 1
            c = 1
            time = T[i]
        elif time - T[i] <= K:
            c += 1
        i += 1

    print(str(bus))

main()
if __name__=="__main__":
    a, b = list(map(int, input().split(" ")))
    if(a == 1):
	a = 14
    if(b == 1):
	b = 14
    if(a > b):
        print("Alice")
    elif(a == b):
        print("Draw")
    else:
        print("Bob")

### FIXED CODE ###

if __name__=="__main__":
    a, b = list(map(int, input().split(" ")))
    if(a==1):
        a = 14
    if(b==1):
        b = 14
    if(a > b):
        print("Alice")
    elif(a == b):
        print("Draw")
    else:
        print("Bob")
s = str(input())
k = int(input())

def func(s, k):
    ans = 0
    n = len(s)
    s_list = list(s)
    for i in range(n - 1):
        if s_list[i] == s_list[i + 1]:
            ans += 1
            s_list[i + 1] = str(i + 1)
    ans *= k
    if s_list[0] == s_list[n - 1]:
        ans += k - 1
    return ans

ans1 = func(s, k)
s_inv = ''.join(list(reversed(s)))
ans2 = func(s_inv, k)

if len(s) % 2 == 1:
    check = True
    for i in range(len(s) - 1):
        if s[i] == s[i + 1]:
            pass
        else:
            check = False
            break
if check:
    ans3 = len(s) * k // 2
else:
    ans3 = ans1

print(min(ans1, ans2, ans3))

### FIXED CODE ###

s = str(input())
k = int(input())

def func(s, k):
    ans = 0
    n = len(s)
    s_list = list(s)
    for i in range(n - 1):
        if s_list[i] == s_list[i + 1]:
            ans += 1
            s_list[i + 1] = str(i + 1)
    ans *= k
    if s_list[0] == s_list[n - 1]:
        ans += k - 1
    return ans

ans1 = func(s, k)
s_inv = ''.join(list(reversed(s)))
ans2 = func(s_inv, k)

if len(s) % 2 == 1:
    check = True
    for i in range(len(s) - 1):
        if s[i] == s[i + 1]:
            pass
        else:
            check = False
            break
    if check:
        ans3 = len(s) * k // 2
    else:
        ans3 = ans1
else:
    ans3 = ans1

print(min(ans1, ans2, ans3))
#D - Grid Repainting
#最短距離のルートを記録してあとはすべて黒く塗る
import copy
import sys
from collections import deque]
#幅優先のロジックを作成する
H,W = (int(i) for i in input().split())
s_tmp = []
for _ in range(H):
    s_tmp.append(list(input()))
d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
q = deque()
q_old = deque()
s = copy.deepcopy(s_tmp)
q.append([0,0,0])
s[H-1][W-1] = 'g'
s[0][0] = 's'
flg = False
while len(q) > 0:
    #print(q)
    node = q.popleft()#qから左端を取り出す(幅優先)
    if node is not None:
        y = node[0]
        x = node[1]
        z = node[2]
        s[y][x] = '#'
        #上下を探索して移動できるところをスタックする
        for dx, dy in d:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < W and 0 <= ny < H) or s[ny][nx] == '#':
                continue
            else:
                tmp = [ny,nx,z+1]
                if s[ny][nx] != 'y':
                    q.append(tmp)
                if s[ny][nx] == 'g' and flg == False:
                    #print(z+1)
                    flg = True
                    sys.exit()
                s[ny][nx] = 'y'
cnt = 0
for j in range(W):
    for i in range(H):
        if s_tmp[i][j] =='.':
            cnt += 1
if flg == False:
    print(-1)
else :
    print(cnt-z-2)

### FIXED CODE ###

#D - Grid Repainting
#最短距離のルートを記録してあとはすべて黒く塗る
import copy
import sys
from collections import deque
#幅優先のロジックを作成する
H,W = (int(i) for i in input().split())
s_tmp = []
for _ in range(H):
    s_tmp.append(list(input()))
d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
q = deque()
s = copy.deepcopy(s_tmp)
q.append([0,0,0])
s[H-1][W-1] = 'g'
s[0][0] = 's'
flg = False

def result():
    cnt = 0
    for j in range(W):
        for i in range(H):
            if s_tmp[i][j] =='.':
                cnt += 1
    if flg == False:
        print(-1)
    else :
        print(cnt-z-2)
        
while len(q) > 0:
    #print(q)
    node = q.popleft()#qから左端を取り出す(幅優先)
    if node is not None:
        y = node[0]
        x = node[1]
        z = node[2]
        s[y][x] = '#'
        #上下を探索して移動できるところをスタックする
        for dx, dy in d:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < W and 0 <= ny < H) or s[ny][nx] == '#':
                continue
            else:
                tmp = [ny,nx,z+1]
                if s[ny][nx] != 'y':
                    q.append(tmp)
                if s[ny][nx] == 'g' and flg == False:
                    #print(z+1)
                    flg = True
                    result()
                    sys.exit()
                s[ny][nx] = 'y'
if flg == False:
        print(-1)
import functools
import math

n,x=map(int,input().split())
z=[]

y=[]
z=list(map(int, input().split()))
z.append(x)

z.sort()
for i in range(n):
  y.append(z[i+1]-z[i])
  
gcd = functools.reduce(math.gcd, y)
print(gcd)


### FIXED CODE ###

import fractions

n,x=map(int,input().split())
z=[]
y=[]
z=list(map(int, input().split()))

for i in range(n):
  y.append(abs(x-z[i]))

if n==1:
  print(y[0])
else:
  gcm=y[0]
  for i in range(n):
    gcm=fractions.gcd(gcm,y[i])
  print(gcm)
N = int(input())
    D = []

    for _ in range(N):
        D.append(int(input()))

    print(len(set(D)))


### FIXED CODE ###

N = int(input())
D = []

for _ in range(N):
  D.append(int(input()))
print(len(set(D)))
##C
A,B = map(float,input().split())
A = int(A)
B = int(B.replace('.',''))
print((A*B)//100)

### FIXED CODE ###

##C
A,B = map(str,input().split())
A = int(A)
B = int(B.replace('.',''))
print((A*B)//100)
A, B, X = map(int, inpput().split())
print("YES" if A+B >= X else "NO")

### FIXED CODE ###

A, B, X = map(int, input().split())
print("YES" if A <= X and A+B >= X else "NO")
import sys

x = []
for _ in range(3):
    x.extend(list(map(int,input().split())))
cnt = [0]*4
for i in range(6):
    cnt[x[i]-1] += 1
for a in cnt:
    if a > 2:
        print("NO")
        sys.exit(1)
print("YES")


### FIXED CODE ###

x = []
f  = 1
for _ in range(3):
    x.extend(list(map(int,input().split())))
cnt = [0]*4
for i in range(6):
    cnt[x[i]-1] += 1
for a in cnt:
    if a > 2:
        f = 0
if f:
    print("YES")
else:
    print("NO")
paper = [0 for i in range(100)]
white_points = None
deep_points = None

def small(x, y):
    p = [[x, y]]
    for i, j in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
        p.append([x + i, y + j])
    return p

def middle(x, y):
    p = small(x, y)
    for i, j in zip([1, -1, 1, -1], [1, 1, -1, -1]):
        p.append([x + i, y + j])
    return p

def big(x, y):
    p = middle(x, y)
    for i, j in zip([-2, 0, 2, 0], [0, -2, 0, 2]):
        p.append([x + i, y + j])
    return p

while True:
    try:
        x, y, size = map(int, input().split(','))
    except:
        print(paper.count(0))
        print(max(paper))
        break

    if size == 1:
        bp = small(x, y)
    elif size == 2:
        bp = middle(x, y)
    elif size == 3:
        bp = big(x, y)
    for p in bp:
        if not 0 <= p[0] * 10 + p[1] <= 99: continue
        paper[p[1] * 10 + p[0]] += 1

### FIXED CODE ###

#!/usr/bin/python

paper = [[0] * 10 for i in range(10)]

def small(x, y):
    p = [[x, y]]
    for i, j in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
        p.append([x + i, y + j])
    return p

def middle(x, y):
    p = small(x, y)
    for i, j in zip([1, -1, 1, -1], [1, 1, -1, -1]):
        p.append([x + i, y + j])
    return p

def big(x, y):
    p = middle(x, y)
    for i, j in zip([-2, 0, 2, 0], [0, -2, 0, 2]):
        p.append([x + i, y + j])
    return p

while True:
    try:
        x, y, size = map(int, input().split(','))
    except:
        break

    if size == 1:
        bp = small(x, y)
    elif size == 2:
        bp = middle(x, y)
    elif size == 3:
        bp = big(x, y)
    for p in bp:
        if 0 <= p[0] < 10 and 0 <= p[1] < 10:
            paper[p[1]][p[0]] += 1

print(sum(paper[y][x] == 0 for y in range(10) for x in range(10)))
print(max(paper[y][x] for y in range(10) for x in range(10)))
import math
N,M=int(input())
def combination(n,r):
    return math.factrial(n)//math.factrial(n-r)*math.factrial(r)
if N>=2 and M>=2:
    print(combination(N,2)+combination(M,2))
elif N>=2 and M<=2:
    print(combination(N,2))
else:
    print(combination(M,2))

### FIXED CODE ###

N,M=map(int,input().split())
print(N*(N-1)//2+M*(M-1)//2)
from collections import defaultdict
N,M=map(int,input().split())
dic = defaultdict(lambda:0)
A = [int(x) for x in input().split()]
length = len(A)
for i in A:
  dic[i] += 1
for i in range(M):
  b,c = map(int,input().split())
  dic[c] += b
A = list(d.items())
A.sort(reverse=True)
ans = 0
l = length
for v,c in A:
  tmp = min(l, c)
  ans += tmp * v
  l -= tmp
print(ans)

### FIXED CODE ###

read = input 
rn = lambda :map(int, read().split())
n,m = rn()
A = list(rn())
l = len(A)
d = {}
for x in A:
    if x not in d:
        d[x]=0
    d[x] += 1
for i in range(m):
    b, c = rn()
    if c not in d:
        d[c]=0
    d[c] += b
A = list(d.items())
A.sort(reverse=True)
ans = 0
cnt = l
# print(A)
for v, c in A:
    tmp = min(cnt, c)
    ans += tmp * v
    cnt -= tmp
print(ans)
A, B, C = stdin.readline().rstrip().split()
answer_1 = A + B
answer_2 = A + C
answer_3 = B + C

print(max(answer_1,answer_2,answer_3))

### FIXED CODE ###

S = input().split()  

A = int(S[0])
B = int(S[1])
C = int(S[2])
answer_1 = A + B
answer_2 = A + C
answer_3 = B + C

print(min(answer_1,answer_2,answer_3))
K = input()
S = input()
count = 0
 
for x in range(K+1):
  for y in range(K+1):
    z = S - x - y
    if 0 <= z and z <= K:
    	count = count + 1
        
print(count)

### FIXED CODE ###

K, S = map(int, input().split())
count = 0
 
for x in range(K+1):
  for y in range(K+1):
    z = S - x - y
    if 0 <= z and z <= K:
    	count += 1
print(count)
n=int(input())
A=list(map(int,input().split()))
m=sum(A)//n
print(max(sum(map(lambda x:(x-m)**2,A)),sum(map(lambda x:(x-m-1)**2,A)))

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
m=sum(A)//n
print(min(sum(map(lambda x:(x-m)**2,A)),sum(map(lambda x:(x-m-1)**2,A))))
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path
read = sys.stdin.read

N, *ab = map(int, read().split())

graph = csr_matrix(([1] * (N - 1), (ab[::2], ab[1::2])), shape=(N + 1, N + 1))
distance = shortest_path(graph, directed=False, indices=[1, N])
d1 = distance[0]
dn = distance[1]

Fennec = -1
for i, j in zip(d1, dn):
    if i <= j:
        Fennec += 1

if Fennec > N - Fennec:
    print('Fennec')
else:
    print('Sunuke')

### FIXED CODE ###

import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
read = sys.stdin.read

N, *ab = map(int, read().split())
a, b = zip(*zip(*[iter(ab)] * 2))

graph = csr_matrix(([1] * (N - 1), (a, b)), shape=(N + 1, N + 1))
distance = dijkstra(graph, directed=False, indices=[1, N])
d1 = distance[0]
dn = distance[1]

Fennec = -1
for i, j in zip(d1, dn):
    if i <= j:
        Fennec += 1

if Fennec > N - Fennec:
    print('Fennec')
else:
    print('Snuke')
#ABC144 B
N=int(input())
S=input()
#print(N)
result=0

for i in range(N-1):
    if S[i]=="A" and S[i+1]=="B" and S[i+2]=="C":
        print(i)
        result+=1
    else:
        print("after"+str(i))
        p=1

print(result)

### FIXED CODE ###

#ABC144 B
N=int(input())
S=input()
#print(N)
result=0

for i in range(N-2):
    if S[i]=="A" and S[i+1]=="B" and S[i+2]=="C":
        #print(i)
        result+=1
    else:
        #print("after"+str(i))
        p=1

print(result)
A,B=map(int,input().split())
if A>(2*B):
    print(A-(2*B)
else:
    print(0)

### FIXED CODE ###

A, B = map(int, input().split())
if A > (2 * B):
    print(A - (2 * B))
else:
    print(0)
import itertools
n = int(input())
a = tuple([int(i) for i in input().split()])
b = tuple([int(i) for i in input().split()])

l = list(itertools.permutations(range(1,n+1)))

print(abs(l.index(a) - l.index(b)))





### FIXED CODE ###

import math
import itertools

n = int(input())
x, y = [0]*n, [0]*n
for i in range(n):
    a, b = map(int, input().split())
    x[i], y[i] = a, b
l = list(itertools.permutations(range(n)))

tmp = 0
for p in l:
    for j in range(n-1):
        a = p[j]
        b = p[j+1]
        tmp += math.sqrt((x[a]-x[b])**2 + (y[a]-y[b])**2)

print(round(tmp/len(l), 10))
input_lst = readline().split(' ')
cand = int(input_lst[1]) - 2 * int(input_lst[0])
print(max(0, cand))

### FIXED CODE ###

input_lst = input().split(' ')
cand = int(input_lst[0]) -  2 * int(input_lst[1])
print(max(0, cand))
k = int(input)
l = [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]
print(l[k-1])

### FIXED CODE ###

k = int(input())
li = [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]
print(li[k-1])
while 1:
	n = input()
	if n == 0: break
	ans = {}
	for i in range(n):
		group,name = raw_input().split(":")
		if i == 0: first = group
		ans[group] = set(name[:-1].split(","))
		while 1:
			for key in ans:
				flag = 0
				for key1 in ans:
					if key in ans[key1]:
						ans[key1] |= ans[key]
						ans[key1].discard(key)
						flag = 1
				if flag:
					del ans[key]
					break
			if flag == 0: break
	print len(ans[first])

### FIXED CODE ###

while 1:
	n = input()
	if n == 0: break
	ans = {}
	for i in range(n):
		group,name = raw_input().split(":")
		if i == 0: first = group
		ans[group] = set(name[:-1].split(","))
	while 1:
		for key in ans:
			flag = 0
			if key == first: continue
			for key1 in ans:
				if key in ans[key1]:
					ans[key1] |= ans[key]
					ans[key1].discard(key)
					flag = 1
			if flag:
				del ans[key]
				break
		if flag == 0: break
	print len(ans[first])
N = int(input())
value_list = input().split()
value_list.sort()
i = 0
#value_list.reverse()
#print(value_list)
for i in range(N):
	if i == 0:
		new_value = int(value_list[i])
	else:
		new_value = (new_value + int(value_list[i])) / 2

print(new_value)

### FIXED CODE ###

a = int(input())
s = input()
if a < 3200:
  s = 'red'
print(s)
X=list(map(int,input().split()))
#X軸に並行
if X[2]-X[0]==0:
    if X[3]-X[1]>0:
        q=X[3]-X[1]
        U="U"
        D="D"
    else:
        q=X[1]-X[3]
        U="U"
        D="D"
    print(U*(q+1)+R*2+D*(q+2)+L*2+U+L+U*q+R*2+D*q+L)
#Y軸に並行
if X[3]-X[1]==0:
    if X[2]-X[0]>0:
        p=X[2]-X[0]
        R="R"
        L="L"
    else:
        p=X[0]-X[2]
        R="L"
        L="R"
    print(R*(p+1)+U*2+L*(p+2)+D*2+R+D+R*p+U*2+L*p+D)

if X[2]-X[0]!=0 or X[3]-X[1]!=0
    if X[2]-X[0]>0:
        p=X[2]-X[0]
        R="R"
        L="L"
    else:
        p=X[0]-X[2]
        R="L"
        L="R"
    if X[3]-X[1]>0:
        q=X[3]-X[1]
        U="U"
        D="D"
    else:
        q=X[1]-X[3]
        U="D"
        D="U"
    print(U*p+R*(q+1)+D*(p+1)+L*(q+1)+U+L+U*(p+1)+R*(q+1)+D*(p+1)+L*q)  

### FIXED CODE ###

sx, sy, tx, ty = map(int, input().split())

higth = ty - sy
width = tx - sx

ans = ''
ans += 'U' * higth
ans += 'R' * width
ans += 'D' * higth
ans += 'L' * width
ans += 'L' + 'U' * (higth + 1)
ans += 'R' * (width + 1) + 'D'
ans += 'R' + 'D' * (higth + 1)
ans += 'L' * (width + 1) + 'U'
print(ans)
A,B,C = map(int, input())
print(min(C,B//A))

### FIXED CODE ###

A,B,C = map(int, input().split())
print(min(C,B//A))
import  math
lis = []

N,M = [int(i) for i in input().split()]

for i in range(1,int(math.sqrt(M))):
    if M % i == 0:
        lis.append(i)
        lis.append(M//i)

lis.sort()
ret = 0
for i in lis:

    ret = i
    if i >= N:
        break

print(M//ret )


### FIXED CODE ###

import  math
lis = []

N,M = [int(i) for i in input().split()]

for i in range(1,int(math.sqrt(M))):
    if M % i == 0:
        lis.append(i)
        lis.append(M//i)


lis.sort()
i =1
for i in lis:
    if i >= N:
        break

print(M//i )
# -*- coding: utf-8 -*-

from scipy.misc import comb
import sys
sys.setrecursionlimit(10000000000)


class UnionFind:

    def __init__(self, n):
        # parent[x] < 0 means x is root and abs(parent[x]) == size[x]
        self.parent, self.depth = [-1] * (n + 1), [0] * (n + 1)

    def find(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)

        if self.depth[x] > self.depth[y]:
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        else:
            self.parent[y] += self.parent[x]
            self.parent[x] = y
            if self.depth[x] == self.depth[y]:
                self.depth[y] += 1

    def count(self, x):
        return - self.parent[self.find(x)]


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

AB = [tuple(map(int, input().split())) for _ in range(M)]
AB.reverse()

groups = UnionFind(N)
ans = [comb(N, 2, exact=True)]
for i in range(M):
    if groups.isSame(AB[i][0], AB[i][1]):
        ans.append(ans)
    else:
        ans.append(ans[-1] - groups.count(AB[i][0]) * groups.count(AB[i][1]))
        groups.union(AB[i][0], AB[i][1])

for i in range(M):
    print(ans[-(i + 2)])


### FIXED CODE ###

# -*- coding: utf-8 -*-

from scipy.misc import comb
import sys
sys.setrecursionlimit(1000000000)


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.depth = [1] * (n + 1)
        self.count = [1] * (n + 1)

    def find(self, x):
        if self.parent[x] == x:
            if self.depth[x] > 2:
                self.depth[x] = 2
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            self.depth[x], self.count[x] = 0, 0
            return self.parent[x]

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

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

        if self.depth[x] < self.depth[y]:
            self.parent[x] = self.parent[y]
            self.count[y] += self.count[x]
            self.depth[x], self.count[x] = 0, 0
        else:
            self.parent[y] = self.parent[x]
            self.count[x] += self.count[y]
            self.depth[y], self.count[y] = 0, 0
            if self.depth[x] == self.depth[y]:
                self.depth[x] += 1


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

A, B = [], []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

A.reverse()
B.reverse()

groups = UnionFind(N)
ans = [comb(N, 2, exact=True)]
for i in range(M):
    tmp = ans[-1]
    if not groups.isSame(A[i], B[i]):
        nA, nB = groups.count[groups.find(
            A[i])], groups.count[groups.find(B[i])]
        tmp -= nA * nB
        groups.union(A[i], B[i])
    ans.append(tmp)

for i in range(M):
    print(ans[-(i + 2)])