Harryxun/stf_run huggingface dataset:
import functools
import math

n, X = map(int, input().split())
x = input().split()
x = [int(m) for m in x]

z = x
z.append(X)
z.sort()

w = []

for i in range(n + 1):
    if i != 0:
        w.append(z[i] - z[i - 1])

gcd = functools.reduce(math.gcd, w)
print(gcd)

### FIXED CODE ###

n, X = map(int, input().split())
x = input().split()
x = [int(m) for m in x]

z = x
z.append(X)
z.sort()

w = []

for i in range(n + 1):
    if i != 0:
        w.append(z[i] - z[i - 1])

n1=len(w)

#ユークリッド互除法の関数の定義
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)


if n1==1:
    print(w[0])
else:
    element = gcd(w[0], w[1])
    if n1==2:print(element)
    else:
        for i in range(2,n1):
            element=gcd(element,w[i])
        print(element)
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <vector>

#define REP(i,n) for(int i=0;i<n;i++)
#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


using namespace std;
using ll=long long;
ll mod = 1e9 + 7;

//int dp[1e5];
//memset(dp, BMAX*HMAX, sizeof(dp));
  
int main() {
    int H, N;
    cin >> H >> N;
    vector<int> A(N), B(N);
    for(int i=0;i<N;i++){
        cin >> A[i] >> B[i];
    }
    vector<ll> dp(H+1, 1e9);
    dp[0] = 0;
    for(int i=0;i<H;i++){
        for(int j=0;j<N;j++){
            chmin(dp[min(i+A[j], H)], dp[i]+B[j]);
        }
    }
    cout << dp[H] << endl;
	return 0;
}


### FIXED CODE ###

import sys

input = sys.stdin.readline
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]

max_damage = max(damage for damage, cost in magic)
dp = [0] * (H + max_damage)

for x in range(1, H + max_damage):
    dp[x] = min(dp[x - damage] + cost for damage, cost in magic)

ans = min(dp[H:])

print(ans)
T = input('Tの入力')
X = input('Xの入力')
t = int(T) / int(X)
print(t)

### FIXED CODE ###

import sys
T,X = [int(n) for n in input().split()]

print(T/X)
n = int(input())
pos = []
for _ in range(n):
  x,y = map(int,input().split())
  pos.append((x,y))

import math
def distance(p1,p2):
  x1,y1 = p1
  x2,y2 = p2
  return math.sprt((x1-x2)**2 + (y1-y2)**2)
  
ans = 0
for i in range(n):
  for j in range(n):
    ans += distance(pos[i],pos[j])
print(ans/n)

### FIXED CODE ###

import math
n = int(input())
points = []
for i in range(n):
  x,y = map(int,input().split())
  points.append((x,y))

def distance(p1,p2):
  ans = (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2
  return math.sqrt(ans)

amount = 0
for i in range(len(points)):
  for j in range(len(points)):
    if i == j:
      continue
    amount += distance(points[i],points[j])
print(amount/n)
str = input().split()
a = int(str[0])
b = int(str[1])
k = int(str[2])

x = max(0,a-k)
if x == 0:
    y = b + a - k

print(x,y)


### FIXED CODE ###

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

x = max(0,a-k)
y = b;
if x == 0:
    y = max(0, b + a - k)

print(x,y)
A,B,C,K=map(int,input().split())

s = [1]*A+[0]*B+[-1]*C
print(sum(s[:K]))

### FIXED CODE ###

A,B,C,K=map(int,input().split())

a = min(A,K)
t1= K-a
b = min(B,t1)
c = K-a-b

#print(a,b,c)
print(a-c)
N, M = map(int, input().split())
a = set(int(i) for i in input().split())

dp = [0] * (N + 1)
dp[0] = 1

for i in range(1,N+1):
    if i in a:
        dp[i] = 0
        continue
    dp[i] = dp[i-1] + dp[i-2]

print(dp[N])

### FIXED CODE ###

N, M = map(int, input().split())
a = set(int(input()) for i in range(M))

dp = [0] * (N + 1)
dp[0] = 1

for i in range(1,N+1):
    if i in a:
        dp[i] = 0
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

print(dp[N])
import sys
s = sorted(list(str(input())))
t = sorted(list(str(input())), reverse = True)
x = 0
y = 0
for i in range(len(s)):
    if s[i] < t[i]:
        print('Yes')
        sys.exit()
    if s[i] == t[i]:
        x += 1
if x == len(s) and len(s) < len(t):
    print('Yes') 
elif s == t:
    print('No')

### FIXED CODE ###

import sys
s = sorted(list(str(input())))
t = sorted(list(str(input())), reverse = True)
u = min(len(s), len(t))
for i in range(min(len(s), len(t))):
    if s[i] < t[i]:
        print('Yes')
        sys.exit()
    if s[i] > t[i]:
        print('No')
        sys.exit()
if s[0:u] == t[0:u] and len(s) < len(t):
    print('Yes')
elif s[0:u] == t[0:u] and len(s) >= len(t):
    print('No')
import math

A,B,N=map(int,input().split())
list=[]
t=0
if B > N:
    print(math.floor(A*N/B))
else:
    for x in range(B+1,N):
        if t==0:
            y=math.floor(A*x/B)-A*math.floor(x/B)
        else:
            z=math.floor(A*x/B)-A*math.floor(x/B)
            if y - z>0:
                y = z
            else:
                break

    print(y)


### FIXED CODE ###

import math

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

if B==1:
    print(0)
else:
    if B > N:
        print(math.floor(A*N/B))

    else:
        print(math.floor(A*(B-1)/B))
n,k=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
mod=10**9+7
total=0
from math import factorial
for i in range(n-k+1):
   f=int((factorial(n-i-1)/factorial(k-1)/factorial(n-k-i)))%mod
   total+=int((l[n-i-1]-l[i])*f)
   total%=mod
print(total)


### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
mod=10**9+7
n_max=2*10**5
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod
total=0
for i in range(n-k+1):
   f=comb(n-i-1,k-1)%mod
   total+=int((l[n-i-1]-l[i])*f)
   total%=mod
print(total)
import itertools
import math
n, a, b, k = map(int, input().split())
count = 0
for i in range(math.floor(n/a)):
    if (n - (i * a)) % b == 0:
        count += (itertools.combinations(n, i) * itertools.combinations(n, (n-i*a)/b))
print(count/998244353)

### FIXED CODE ###

N,A,B,K = map(int,input().split())
sprime = 998244353 # approx 10**9
A,B = sorted((A,B))
if (A+B) * N < K:
	print(0)
	exit()
 
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
 
memo = [0] * (N+1)
memo[0] = memo[N] = 1
for i in range(1,N//2+1):
	v = memo[i-1] * (N-i+1) * modinv(i,sprime)
	v = v % sprime
	memo[i] = memo[N-i] = v
 
# max is A*N + B*N
sum = 0
for b in range(N+1):
  a = (K-b*B)//A
  if 0 <= a <= N and a*A+b*B == K:
    sum += memo[a]*memo[b]
    sum %= sprime
 
print(sum)
S = input()
print(700 + S.count(o) * 100)

### FIXED CODE ###

S = input()
print(700 + S.count("o") * 100)
n = int(input())
table = map(int,input().split())
print("{} {} {}".format(max(table[n],min(table[n],sum(table[n])))))


### FIXED CODE ###

n = input()
table = list(map(int,input().split()))
print("{} {} {}".format(min(table),max(table),sum(table)))
mod=10**9+7
n=int(input())
l=list(map(int,input().split()))
ans=1
rgb=[0,0,0]
for i in range(n):
    for j in range(3):
        c=0
        if l[i]==rgb[0]:
            c+=1
    p=rbg.index(l[i])
    rgb[p]+=1
    ans*=c
    ans%=mod
print(ans)
    

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
mod=10**9+7
ans=1
rgb=[0]*3
for i in range(n):
    f=0
    for j in range(3):
        if l[i]==rgb[j]:
            if f==0:
                rgb[j]+=1
            f+=1
    ans*=f
    ans%=mod
print(ans)
a, b = map(int, input().split())
  if a*b % 2 == 0:
    print("Even")
  else:
    print("Odd")

### FIXED CODE ###

a, b = map(int, input().split())
print("Odd" if a * b % 2 else "Even")
n,maxg=map(int,input().split())
lista =[int(input()) for i in range(n)]
count=count+n
nokori=maxg-sum(lista)
print(count)
while nokori-min(lista)>=0:
    nokori=nokori-min(lista)
    count+=1
print(count)

### FIXED CODE ###

n,maxg=map(int,input().split())
lista =[int(input()) for i in range(n)]
count=n
nokori=maxg-sum(lista)

while nokori-min(lista)>=0:
    nokori=nokori-min(lista)
    count+=1
print(count)
N=int(input())
x=N*800
y=N//15*200
S=x-y
print(S)v

### FIXED CODE ###

N=int(input())
x=N*800
y=N//15*200
S=x-y
print(S)
n = int(input())
t = []
ans = 1
for i in range(n):
    t.append(int(input()))
def gcd(a,b):
    while b>0:
        a,b = b, a%b
    return int(a)
def lcm(a,b):
    return int(a*b/gcd(a,b))

for i in range(n):
    ans = lcm(ans,t[i])

print(ans)

### FIXED CODE ###

n = int(input())
t = []
ans = 1
for i in range(n):
    t.append(int(input()))
def gcd(a,b):
    while b>0:
        a,b = b, a%b
    return a
def lcm(a,b):
    return a*b//gcd(a,b)

for i in range(n):
    ans = lcm(ans,t[i])

print(ans)
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    a = list(map(int, input().split()))
    def Chk(a, pos):
        cnt = 0
        tmp = 0

        for a in A:
            tmp += a

            if pos and tmp < 1:
                cnt += 1 - tmp
                tmp = 1
            elif not pos and tmp > -1:
                cnt += 1 + tmp
                tmp = -1

            pos = not pos
        return cnt

    print(min(Chk(A, True), Chk(A, False)))
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

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

def Chk(a, pos):
    cnt = 0
    tmp = 0

    for a in A:
        tmp += a

        if pos and tmp < 1:
            cnt += 1 - tmp
            tmp = 1
        elif not pos and tmp > -1:
            cnt += 1 + tmp
            tmp = -1

        pos = not pos
    return cnt

print(min(Chk(A, True), Chk(A, False)))
n = int(input())
s = input()
ans = 0
for i in range(n):
    if s[i] == 'A' and s[i+1] == 'B' and s[i+2] == 'C':
        ans += 1
        
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(n-2):
    if s[i] == 'A' and s[i+1] == 'B' and s[i+2] == 'C':
        ans += 1
        
print(ans)
H, N = input().split(" ")
A = list(map(int, input().split()))
if sum(A) < H:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

H, N = input().split(" ")
A = list(map(int, input().split()))
if sum(A) < int(H):
  print("No")
else:
  print("Yes")
n, k = map(int, input().split())
a = list(map(int, input().split()))
rec = [0]
i = 0
flag = [0 for _ in range(n + 1)]
while True:
    if flag[rec[i]] == 0:
        flag[a[i]] = 1
        rec.append(a[rec[i]] - 1)
    else:
        start = rec.index(a[rec[i]] - 1)
        loop = rec[start:]
        pre = rec[:start]
        break
    i += 1
count = (k - len(pre)) % len(loop)
print(loop[count] + 1)


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
rec = [0]
i = 0
flag = [0 for _ in range(n + 1)]
while True:
    if flag[rec[i]] == 0:
        flag[rec[i]] = 1
        rec.append(a[rec[i]] - 1)
    else:
        start = rec.index(a[rec[i]] - 1)
        loop = rec[start:]
        pre = rec[:start]
        break
    i += 1
count = (k - len(pre)) % len(loop)
if k <= len(pre):
    print(pre[k] + 1)
else:
    print(loop[count] + 1)
def lcs():
???x, y = raw_input()
???x_len = len(x)
???y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

???for j in range(x_len):
    ???z1 = z2 + []
      for k in range(y_len):
         if x[k] = y[k]:
            z2[k+1] = z2[k] + 1
         elif z2[j+1] = z2[j]:???
?????????      z2[j+1] = z2[j]

  return z2[-1]

num = input()
for l in range(num):
   print lcs()

### FIXED CODE ###

def lcs():
  x = raw_input()
  y = raw_input()
  x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

  for i in range(x_len):
    z1 = z2 + []
    ele = x[i]
    for k in range(y_len):
      if ele == y[k]:
        z2[k+1] = z1[k] + 1
      elif z2[k+1] < z2[k]:
        z2[k+1] = z2[k]

  return z2[-1]

num = input()
for j in range(num):
  print lcs()
a, s = input().split()
if a >= 3200:
  print('red')
else:
  print(a)

### FIXED CODE ###

a, s = open(0).read().split()
if int(a) >= 3200:
  print(s)
else:
  print('red')
N = int(input())
A = list(map(int, input().split()))

for i in range(N):
    A[i] -= i+1

A.sort()
print(A)
median = A[N//2]

for i in range(N):
    A[i] -= median
    A[i] = abs(A[i])
print(sum(A))

### FIXED CODE ###

N = int(input())
print(N if N%2 == 0 else N*2)
N,M,C = map(int,input().split())
B = list(map(int,input().split()))
count = 0
for i in range(N):
  a = list(int,input().split())
  for j in range(M):
  P = C  
  P += B[j]*a[j]
  if P>0:
    count+=1
print(count)

### FIXED CODE ###

N,M,C = map(int,input().split())
B = list(map(int,input().split()))
count = 0
for i in range(N):
  a = list(map(int,input().split()))
  P = C  
  for j in range(M):
    P += B[j]*a[j]
  if P>0:
    count+=1
print(count)
n,k = map(int, input().split())
list_x = list((map(int, input().split())))
ans = 10**9
for i in range(0,n-k+1):
    prob_list = list_x[i:i+k]
    if list_x[i+k-1] < 0 and list_x[i+k] < 0 and i != n-k-1 :
        continue
    elif list_x[i] > 0 and list_x[i-1] > 0 and i != 0:
        continue
    dist = min(abs(list_x[i]),abs(list_x[i+k-1])) + (list_x[i+k-1] - list_x[i])
    if ans > dist:
        ans = dist
print(ans)


### FIXED CODE ###

def binarySearch(list_a, key):
    left = 0
    right = len(list_a)
    while left < right:
        mid = (left + right) // 2
        if list_a[mid] == key:
            return mid
            break
        elif key < list_a[mid]:
            right = mid
        else:
            left = mid+1
    else:
        return mid

n,k = map(int, input().split())
list_x = list((map(int, input().split())))
ans = 10**9
key_point = binarySearch(list_x,0)
for i in range(key_point-k,key_point+1):
    if i < 0:
        continue
    try:
        dist = min(abs(list_x[i]),abs(list_x[i+k-1])) + (list_x[i+k-1] - list_x[i])
        if ans > dist:
            ans = dist
    except:
        pass
print(ans)
n, *a = map(int, open(0).read().split())
s = [i%4 for a]
f, k = s.count(0), s.count(2)
print("YNeos"[n-f-k > f+(k>0)::2])

### FIXED CODE ###

n, *a = map(int, open(0).read().split())
s = [i%4 for i in a]
f, t = s.count(0), s.count(2)
print("YNeos"[n-f-t+(t>0) > f+1::2])
n = input()

for i in range(n):
  print(bin(n))


### FIXED CODE ###

n = input()
b_l = []
for i in range(8):
  b = bin(i)[2:]
  le = len(b)
  b_l.append((3 - le)*"0" + b)


    

s_l = [int(n[i]) for i in range(4)]
    
for b in b_l:
  ans = s_l[0]
  f = 0
  b_s_l = ["+" if b[i] == "0" else "-" for i in range(3)]
  for i in range(3):
    if b_s_l[i] == "+":
      ans += s_l[i+1]
    else:
      ans -= s_l[i+1]
  if ans == 7:
    print(str(s_l[0]) + b_s_l[0] + str(s_l[1]) + b_s_l[1] + str(s_l[2]) + 
          b_s_l[2] + str(s_l[3]) + "=7") 
    break
H,W = map(int, input().split())

S = ["" for _ in range(H)]
for i in range(H):
    S[i] = input()

INF = float("inf")
dp = [[INF for _ in range(H*W)] for _ in range(H*W)]

for i in range(H):
    for j in range(W):
        
        if j != W-1 and S[i][j] == "." and S[i][j+1] == ".":
            dp[(H*i)+j][(H*i)+j+1] = 1
            dp[(H*i)+j+1][(H*i)+j] = 1

        if i != H-1 and S[i][j] == "." and S[i+1][j] == ".":
            dp[(H*i)+j][(H*(i+1))+j] = 1
            dp[(H*(i+1))+j][(H*i)+j] = 1
    
        dp[(H*i)+j][(H*i)+j] = 0


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

ans = 0
for i in range(N):
    for j in range(N):
        if dp[i][j] != INF:
            ans = max(ans, dp[i][j])
 
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def main():
    H,W = map(int, input().split())

    S = ["" for _ in range(H)]
    for i in range(H):
        S[i] = input()

    INF = float("inf")
    N = H*W
    dp = [[INF for _ in range(N)] for _ in range(N)]

    for i in range(H):
        for j in range(W):
            
            if j != W-1 and S[i][j] == "." and S[i][j+1] == ".":
                dp[(W*i)+j][(W*i)+j+1] = 1
                dp[(W*i)+j+1][(W*i)+j] = 1

            if i != H-1 and S[i][j] == "." and S[i+1][j] == ".":

                dp[(W*i)+j][(W*(i+1))+j] = 1
                dp[(W*(i+1))+j][(W*i)+j] = 1
        
            dp[(W*i)+j][(W*i)+j] = 0


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

    ans = 0
    for i in range(N):
        for j in range(N):
            if dp[i][j] != INF:
                ans = max(ans, dp[i][j])
    
    print(ans)

if __name__ == "__main__":
    main()
N=int(input())
for i in range(1,N+1):
    if i*i>N:
        s=i-1
        break
print(s)

### FIXED CODE ###

N=int(input())
for i in range(1,N+1):
    if i*i>N:
        s=(i-1)**2
        break
if N==1:
    print(N)
else:
    print(s)
import numpy as np

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

A = np.empty(N)
B = np.empty(N)

for i in range(N):
    INPUT_AB = input()
    A[i] = int(INPUT_AB.split(" ")[0])
    B[i] = int(INPUT_AB.split(" ")[1])

num_drink = 0
drink_price = 0

while num_drink < M:
    price = np.amin(A)
    store_index = np.argmin(A)
    num_drink += B[store_index]
    print(num_drink)
    if num_drink >= M:
        num_drink -= B[store_index]
        while num_drink < M:
            num_drink += 1
            drink_price += price
        
    else:
        drink_price += price * B[store_index]
        A = np.delete(A, store_index)
        B = np.delete(B, store_index)

print(drink_price)

### FIXED CODE ###

# 2150 start

import numpy

N,M=map(int, input().split())
price = numpy.empty((N,3))
sumcan = 0
sumprice = 0
lastshop = 0

for i in range(N):
    shop_data = input().split()
    A = int(shop_data[0])
    B = int(shop_data[1])
    price[i,0]= A * B
    price[i,1] = A
    price[i,2] = B

price = price[price[:,1].argsort(),:]

for j in range(M):
    sumcan = sumcan + price[j,2]
    if sumcan < M:
        sumprice = sumprice + price[j,0]
    elif sumcan >= M:
        sumcan = sumcan - price[j,2]
        lastshop = j
        break

sumprice = sumprice + (M - sumcan)*price[lastshop,1]

print(int(sumprice))
s = [*input()]
t = [*input()]
flg = 0

for i in range(len(s)):
    if s != t:
        s.append(s[0])
        s.remove(s[0])
    else:
        flg = 1
        break

if flg == 0:
    print("No")
else:
    print("Yes")


### FIXED CODE ###

s = [i for i in input()]
t = [i for i in input()]
flg = 0

for i in range(len(s)):
    if s != t:
        s.append(s[0])
        s.remove(s[0])
    else:
        flg = 1
        break

if flg == 0:
    print("No")
else:
    print("Yes")
A, B = map(int(input().split()))
if A == B:
  print('Draw')
elif A == 1:
  print('Alice')
elif B == 1:
  print('Bob')
elif A > B:
  print('Alice')
else:
  print('Bob')

### FIXED CODE ###

A, B = map(int, input().split())
if A == B:
  print('Draw')
elif A == 1:
  print('Alice')
elif B == 1:
  print('Bob')
elif A > B:
  print('Alice')
else:
  print('Bob')
import sys

N = int(sys.stdin.readline())


def dev(x):
    global cnt
    if x % 2 == 0:
        cnt += 1
        dev(x / 2)
    return cnt


min_cnt = 0
sorted_list = sorted([2, 4, 8, 16, 32, 64, N], reverse=True)
min_index = sorted_list[sorted([2, 4, 8, 16, 32, 64, N], reverse=True).index(N) + 1]

for i in range(min_index, N + 1, 2):
    cnt = 0
    result = dev(i)
    if min_cnt < result:
        min_i = i
        min_cnt = result
print(min_i)


### FIXED CODE ###

m = int(input())
a = 1
for c in range(7):
  if (2 ** c) > m:
    break
  a = (2 ** c)
 
print(a)
import sys
sys.setrecursionlimit(10000)

def detectGroup(parents,x):
    if parents[x]!=x:
        parents[x]=detectGroup(parents,parents[x])
        return parents[x]
    else:
        return x
    
N,M=map(int,input().split())
AB=[[int(x)-1 for x in input().split()] for i in range(M)][::-1]
parents=[i for i in range(N)]
groupsize=[1 for i in range(N)]
inconv=N*(N-1)/2
result = []
for i in range(M):
    result.append(str(int(inconv))+'\n')
    groupA=detectGroup(parents,AB[i][0])
    groupB=detectGroup(parents,AB[i][1])
    if groupA!=groupB:
        inconv-=groupsize[groupA]*groupsize[groupB]
        groupsize[groupA]+=groupsize[groupB]
    parents[groupB] = groupA
print("".join(result[::-1]))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

def detectGroup(parents,x):
    if parents[x]!=x:
        parents[x]=detectGroup(parents,parents[x])
        return parents[x]
    else:
        return x
    
N,M=map(int,input().split())
AB=[[int(x)-1 for x in input().split()] for i in range(M)][::-1]
parents=[i for i in range(N)]
groupsize=[1 for i in range(N)]
inconv=N*(N-1)/2
result = []
for i in range(M):
    result.append(str(int(inconv))+'\n')
    groupA=detectGroup(parents,AB[i][0])
    groupB=detectGroup(parents,AB[i][1])
    if groupA!=groupB:
        inconv-=groupsize[groupA]*groupsize[groupB]
        groupsize[groupA]+=groupsize[groupB]
    parents[groupB] = groupA
print("".join(result[::-1]))
import sys
sys.setrecursionlimit(10 ** 7)
#f = open('input.txt','r')
input = sys.stdin.readline
#sys.stdin = f

N = int(input())
A = [int(input()) for _ in range(N)]
cntA = [0 for _ in range(max(A)+1)]
for a in A:
    cntA[a] += 1
    cntA[a] %= 2
print(sum(cntA))

### FIXED CODE ###

N = input()
if "9" in N:
    print("Yes")
else:
    print("No")
def check(s, ans, i) :
    return s[i-1] ^ ans[i-2] ^ ans[i]

def solve(first, second, s) :
    n = len(s)
    ans = [0] * (n)
    ans[-2] = first;
    ans[-1] = second;



    for i in range(0, n-2) :
        nsame = 0
        nsame ^= s[i-1]
        nsame ^= ans[i-1]
        ans[i] = ans[i-2] ^ nsame
    if check( s, ans, -2 ) == 0 and check(s, ans, -1) == 0 :
        ans += [1]
#    print(ans)
    return ans

N = int(input())
s = input()

data = [0] * N
for i in range(N) :
    data[i] = 1 if s[i] == 'o' else 0
ok = 0

for i in range(2) :
    if ok == 1 :
        break
    for j in range(2) :
        if ok == 1 :
            break
        ans = solve(i, j, data)
        ok = len(ans) - N
if ok == 0 :
    print("-1")
else :
    for i in range(N) :
        print('S' if ans[i] == 1 else 'W', end = "")
    print()



### FIXED CODE ###


def check(s, ans, i) :
    return s[i-1] ^ ans[i-1] ^ ans[i-2] ^ ans[i]

def solve(first, second, s) :
    n = len(s)
    ans = [0] * (n)
    ans[-2] = first;
    ans[-1] = second;



    for i in range(0, n-2) :
        nsame = 0
        nsame ^= s[i-1]
        nsame ^= ans[i-1]
        ans[i] = ans[i-2] ^ nsame
    if check( s, ans, n-2 ) == 0 and check(s, ans, n-1) == 0 :
        ans.append(1)
#    print(ans)
    return ans

N = int(input())
s = input()

data = [0] * N
for i in range(N) :
    data[i] = 1 if s[i] == 'x' else 0
ok = 0

for i in range(2) :
    if ok == 1 :
        break
    for j in range(2) :
        if ok == 1 :
            break
        ans = solve(i, j, data)
        ok = len(ans) - N
if ok == 0 :
    print("-1")
else :
    for i in range(N) :
        print('W' if ans[i] == 1 else 'S', end = "")
    print()
str = input()
a, b = str.split()
a, b = int(a), int(b)

print(len(str(int(a, b))))


### FIXED CODE ###

a, b = input().split()
a, b = int(a), int(b)
 
digit = 0
for i in range(100):
  if a <= b ** i - 1:
    digit = i
    break
    
print(digit)
a, b, k = map(int, input())
c = min(a,k)
a -= c
k -= c
b -= min(b, k)
print(a, b)

### FIXED CODE ###

a, b = input().split()
print(b + a)
S=input()
if not S[1]==S[2]and S[2]==S[3]:
	print('No')
else:
	print('Yes')

### FIXED CODE ###

S=input()
if S[0]==S[1]and S[1]==S[2]:
	print('No')
else:
	print('Yes')
n=int(input())
h=list(map(int,input().split()))
cnt=0
for i in range(n-1):
  if　h[i]>=h[i+1]:
    a+=1
  else:
    if a>cnt:
      cnt=a
      a=0
print(cnt)

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
cnt=0
a=0
for i in range(n-1):
    if h[i]>=h[i+1]:
        a+=1
    else:
        a=0
    cnt=max(cnt,a)
print(cnt)