Harryxun/stf_run huggingface dataset:
A=input()
B=input()
C=input()
s=a
while len(A)!=0 and len(B)!=0 and len(C)!=0:
  if s=="a":
    if A[0]=="b":
      s="b"
      continue
    if A[0]=="c":
      s="c"
      continue
  elif s=="b":
    if B[0]=="c":
      s="c"
      continue
    if B[0]=="a":
      s="a"
      continue
  else:
    if C[0]=="a":
      s="a"
      continue
    if C[0]=="b":
      s="b"
      continue
if len(A)==0:
  print("A")
elif len(B)==0:
  print("B")
else:
  print("C")

### FIXED CODE ###

A=input()
B=input()
C=input()
s="a"
while (len(A)!=0 or s!="a") and (len(B)!=0 or s!="b") and (len(C)!=0 or s!="c"):
  if s=="a":
    s=A[0]
    A=A[1:]
  elif s=="b":
    s=B[0]
    B=B[1:]
  else:
    s=C[0]
    C=C[1:]
if len(A)==0 and s=="a":
    print("A")
elif len(B)==0 and s=="b":
    print("B")
else:
    print("C")
from decimal import Decimal
a,b,c = list(map(int,input().split()))
a = Decimal(a)
b = Decimal(b)
c = Decimal(c)
A = a**0.5
B = b**0.5
C = c**0.5
AB = A+B
if AB < C:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a,b,c = list(map(int,input().split()))
X = c-a-b
if X > 0 and X*X > 4*a*b:
    print("Yes")
else:
    print("No")
import math

r = int(input())

area = math.pi * (r ** 2)
circum = 2 * math.pi * r

print("{0:.6f} {1:.6f}".format(area, circum))

### FIXED CODE ###

import math

r = float(input())

area = math.pi * (r ** 2)
circum = 2 * math.pi * r

print("{0:.6f} {1:.6f}".format(area, circum))
a, b, k = map(int, input().strip().split(' '))
i = 1
l = []
while len(l)<k:
    if a%i=0 and b%i=0 or i%2=0:
        l.append(i)
    else:
        pass
    i=i+1
print(l[-1])

### FIXED CODE ###

a, b, k = map(int, input().strip().split(' '))
i = 1
l = []
while i<=a or i<=b:
    if a%i==0 and b%i==0:
        l.append(i)
    else:
        pass
    i=i+1
print(l[-k])
N,M = map(int,input().split())
for i in range(M):
    print(str(i+1) + ' ' + str(N-i-1))


### FIXED CODE ###

K = int(input())
A,B = map(int,input().split())
k = (B // K) * K
if A <= k and k <= B:
    print('OK')
else:
    print('NG')
N, M = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(M)]
p = list(map(int, input().split()))
ans = 0

for i in range(2**n):
    bulb = [0] * m
    for j in range(n):
        if i>>j & 1:
            for k in range(m):
                if j+1 in lst[k][1:]:
                    bulb[k] += 1

    flag = True
    for l in range(m):
        if bulb[l] % 2 != p[l]:
            flag = False
    if flag:
        ans += 1

print (ans)


### FIXED CODE ###

n, m = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
ans = 0

for i in range(2**n):
    bulb = [0] * m
    for j in range(n):
        if i>>j & 1:
            for k in range(m):
                if j+1 in lst[k][1:]:
                    bulb[k] += 1

    flag = True
    for l in range(m):
        if bulb[l] % 2 != p[l]:
            flag = False
    if flag:
        ans += 1

print (ans)
n = int(input())
p = list(map(int,input().split()))
a = p[0]
ans = 0
for i in range(n):
  if(m<=p[i]):
    ans += 1
    a = p[i]
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
a = p[0]
ans = 0
for i in range(n):
  if(a>=p[i]):
    ans += 1
    a = p[i]
print(ans)
import itertools

n = int(input())
p = tuple(map(int,input().split()))
q = tuple(map(int,input().split()))
ls = list(itertools.parmutations(range(1,n+1)))
print(abs(ls.index(p)-ls.index(q)))

### FIXED CODE ###

import itertools

n = int(input())
p = tuple(map(int,input().split()))
q = tuple(map(int,input().split()))
ls = list(itertools.permutations(range(1,n+1)))
print(abs(ls.index(p)-ls.index(q)))
n,d=map(int,input().split())

x=[list(map(int,input().split())) for i in range(n)]

lis=[False for i in range(4000)]
for i in range(63):
  lis[i*i]=True
  
ans=0
for i in range(n):
  for j in range(i):
    dis=sum([(x[i][k]-x[j][k])*(x[i][k]-x[j][k]) for k in range(d)])
    if lis[dis]:
      ans += 1
print(ans)

### FIXED CODE ###

n,d=map(int,input().split())

x=[list(map(int,input().split())) for i in range(n)]

lis=[False for i in range(16001)]
i=0
while(i*i<16000):
  lis[i*i]=True
  i+=1
  
ans=0
for i in range(n):
  for j in range(i):
    dis=sum([(x[i][k]-x[j][k])*(x[i][k]-x[j][k]) for k in range(d)])
 #   print(dis)
    if lis[dis]:
      ans += 1
print(ans)
a, b, h, m = map(int, input().split(' '))

rec_h = 30 * h + 0.5 * m
rec_m = 6 * m
rec = (rec_h-rec_m) % 180

x = b * math.sin(math.radians(rec))
y = a - b * math.cos(math.radians(rec))

r = math.sqrt(x**2 + y**2)
print(r)

### FIXED CODE ###

import math
a, b, h, m = map(int, input().split(' '))

rec_h = 30 * h + 0.5 * m
rec_m = 6 * m
rec = abs(rec_h-rec_m)
if rec > 180:
    rec = 360 - rec

x = b * math.sin(math.radians(rec))
y = a - b * math.cos(math.radians(rec))

r = math.sqrt(x**2 + y**2)
print(r)
get=raw_input()
print("YES")

### FIXED CODE ###

get=input()
get = get.split(" ")
flg=0
get=list(set(get))
for a in get:
  if int(a) in[1,9,7,4]:
    flg+=1
    
if flg==4:
  print("YES")
else:
  print("NO")
h,w,d=map(int,input().split())
D=dict()
for i in range(h):
  A=[int(i) for i in input().split()]
  for j in range(w):
    D[A[j]]=[i+1,j+1]
def Dist(x,y):
  return abs(D[x][0]-D[y][0])+abs(D[x][1]-D[y][1])
T=[[0 for _ in range(h*w)] for _ in range(h*w)]
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  ans=0
  rep=(r-l)//d
  for j in range(rep):
    if T[l+j*d][l+(j+1)*d]!=0:
      ans+=T[l+j*d][l+(j+1)*d]
    else:
      ans+=Dist(l+j*d,l+(j+1)*d)
      T[l+j*d][l+(j+1)*d]=Dist(l+j*d,l+(j+1)*d)
  print(ans)

### FIXED CODE ###

h,w,d=map(int,input().split())
D=dict()
for i in range(h):
  A=[int(i) for i in input().split()]
  for j in range(w):
    D[A[j]]=[i+1,j+1]
def Dist(x,y):
  return abs(D[x][0]-D[y][0])+abs(D[x][1]-D[y][1])
T=[[0 for _ in range((h*w)//d)] for _ in range(d)]
for i in range(d):
  for j in range((h*w)//d):
    if i+1+d*(j+1)>h*w:
      continue
    elif j==0:
      T[i][j]=Dist(i+1,i+1+d)
    else:  
      T[i][j]=T[i][j-1]+Dist(i+1+d*j,i+1+d*(j+1))
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  x=l%d
  if r==x:
    print(0)
  elif l==x and x!=0:
    print(T[x-1][(r-x)//d-1])
  elif l==x and x==0:
    print(T[x-1][(r-x)//d-2])
  else:
    ll=(l-x)//d-1
    rr=(r-x)//d-1
    if x==0:
      ll-=1
      rr-=1
    print(T[x-1][rr]-T[x-1][ll])
a, b = list(map(int(input().rstrip())))
if a<8 and b< 8:
  print("Yay!")
else:
  print(":(")

### FIXED CODE ###

a, b = list(map(int, input().rstrip().split()))
if a<= 8 and b <= 8:
    print("Yay!")
else:
    print(":(")
W, H, N = map(int, input().split())

left = 0
right = W
bottom = 0
top = H

for i in range(N):
  x, y, a = map(int, input().split())
  if a == 1:
    left = max(left, x)
  elif a == 2:
    right = min(right, x)
  elif a == 3:
    bottom = max(bottom, y)
  else:
    top = min(top, y)
    
print((right-left) * (top-bottom))

### FIXED CODE ###

abc = list(map(int, input().split()))
abc.sort()
if abc[0]+abc[1] == abc[2]:
  print('Yes')
else:
  print('No')
class Stack(object):
    def __init__(self):
        self.top = 0
        self.data = []

    def is_empty(self):
        return self.top == 0

    def push(self, x):
        self.top += 1
        self.data.append(x)

    def pop(self):
        self.top -= 1
        item = self.data[-1]
        del self.data[-1]
        return item


def do_calc(data):
    s = Stack()  # ??????????????¨??????????????????
    while data:
        elem = data[0]
        data = data[1:]
        if elem == '+' or elem == '-' or elem == '*':
            try:
                a = s.pop()
                b = s.pop()
                if elem == '+':
                    s.push(b + a)
                elif elem == '-':
                    s.push(b - a)
                elif elem == '*':
                    s.push(b * a)
            except IndexError:
                return None
        else:
            s.push(int(elem))
    try:
        result = s.pop()
    except IndexError:
        return None
    else:
        return result


if __name__ == '__main__':
    # ??????????????\???
    data = [int(x) for x in input().split(' ')]
    # data = ['1', '2', '+', '3', '4', '-', '*']

    # ???????????????
    result = do_calc(data)

    # ???????????????
    print(result)

### FIXED CODE ###

def do_calc(data):
    from collections import deque
    s = deque()  # ??????????????¨??????????????????
    while data:
        elem = data[0]  # ?????????????????????????????????

        # ???????????§????????°?????´??????????????????pop??§????????????????¨????????????????????????????????????????
        if elem == '+' or elem == '-' or elem == '*':
            a = s.pop()
            b = s.pop()
            if elem == '+':
                s.append(b + a)
            elif elem == '-':
                s.append(b - a)
            elif elem == '*':
                s.append(b * a)
        # ??°?????§????????°????????????????????????
        else:
            s.append(int(elem))

        # ?¬??????????????????????????????????????????????????????¨??????
        data = data[1:]
    return s.pop()


if __name__ == '__main__':
    # ??????????????\???
    data = [x for x in input().split(' ')]
    # data = ['1', '2', '+', '3', '4', '-', '*']

    # ???????????????
    result = do_calc(data)

    # ???????????????
    print(result)
def dfs(i,pre,n,a,ans):
    if (pre*2 < a[i]): return -1
    ans[i] += a[i]
    if (i == n):
        return a[i]

    pre = pre*2 - a[i]
    u = dfs(i+1,pre,n,a,ans);
    if (u<0 or pre*2 < u): return -1;
    ans[i] += min(pre, u)
    return min(pre, u) + a[i]



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

if (n == 0):
    if (a[0] == 0):
        print(-1)
    else:
        print(1)
    exit()

ans = [1] + [0]*n
u = dfs(1,1,n,a,ans)
if (n!=0 and a[0] != 0): u = -1

if (u >= 0):
    print(sum(ans))
else:
    print(-1)


### FIXED CODE ###

import sys 
sys.setrecursionlimit(2*100000) 

def dfs(i,pre,n,a,ans):
    if (pre*2 < a[i]): return -1
    ans[i] += a[i]
    if (i >= n):
        return a[i]

    pre = pre*2 - a[i]
    u = dfs(i+1,pre,n,a,ans);
    if (u<0 or pre*2 < u): return -1;
    ans[i] += min(pre, u)
    return min(pre, u) + a[i]



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

if (n == 0):
    if (a[0] == 1):
        print(1)
    else:
        print(-1)
    exit()

ans = [1] + [0]*n
u = dfs(1,1,n,a,ans)
if (a[0] != 0): u = -1

if (u >= 0):
    print(sum(ans))
else:
    print(-1)
N,A=map(int,input().split())
if N>A and (N-A)%500==0:
    print("Yes")
elif N<=A:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

N=int(input())
A=int(input())
if N%500<=A:
    print("Yes")
else:
    print("No")
def common():
   X = raw_input()
   Y = raw_input()
           
   for i in range(0. len(X)+1):
      s[i] = 0
           
   for j in range(0, len(X)):
      t = s + []
      for k in range(0, len(Y)):
         if s[j] == j[k]:
            s[k+1] = t[k] + 1
         elif s[k+1] < s[k]:
            s[k+1] = s[k]
        
   return s[-1]
  
q = input()     
for l in range(0, q):
   common()

### FIXED CODE ###

def common():
   X = raw_input()
   Y = raw_input()
  
   s = [0 for i in range(len(Y)+1)]
 
   for j in range(0, len(X)):
      t = s + []
      for k in range(0, len(Y)):
         if X[j] == Y[k]:
            s[k+1] = t[k] + 1
         elif s[k+1] < s[k]:
            s[k+1] = s[k]
  
   print s[-1]
 
q = input()
for l in range(0, q):
   common()
import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
a.sort()
bc.sort(key=lambda x:x[1],reverse=True)
s=0
for i in range(m):
  if a[s]<bc[i][1]:
    t=bisect.bisect_left(a,bc[i][1],s,n)
    for j in range(s,min(t,s+bc[i][0])):
      a[j]=bc[i][1]
    s=min(t,s+bc[i][0])
  else:
    break
print(sum(ans))

### FIXED CODE ###

import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
a.sort()
bc.sort(key=lambda x:x[1],reverse=True)
s=0
for i in range(m):
  if a[s]<bc[i][1]:
    t=bisect.bisect_left(a,bc[i][1],s,n)
    for j in range(s,min(t,s+bc[i][0])):
      a[j]=bc[i][1]
    s=min(t,s+bc[i][0])
    if s>=n:
      break
  else:
    break
print(sum(a))
def make_divisors(n):
    divisors = []
    min_k = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
                k = max(len(str(i)), len(str(n // i)))
                min_k.append(k)

    # divisors.sort()
    return min_k

N = int(input())
# min_k = len(str(N)) + 1
# for i in range(1, N):
#     if N % i != 0:
#         continue
#     if i ** 2 > N:
#         break
#     else:
#         ii = N // i
#         k = max(len(str(i)), len(str(ii)))
#         # print(i, ii, k, min_k)
#         if min_k > k:
#             min_k = k
print(min(make_divisors(N)))

### FIXED CODE ###

def make_divisors(n):
    divisors = []
    min_k = 10
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            k = max(len(str(int(i))), len(str(int(n // i))))
            min_k = min(min_k, k)

    # divisors.sort()
    return min_k

N = int(input())
# min_k = len(str(N)) + 1
# for i in range(1, N):
#     if N % i != 0:
#         continue
#     if i ** 2 > N:
#         break
#     else:
#         ii = N // i
#         k = max(len(str(i)), len(str(ii)))
#         # print(i, ii, k, min_k)
#         if min_k > k:
#             min_k = k
print(make_divisors(N))
# coding UTF-8
# 
# problem C
# 

import pandas as pd

t = []
N, M = map(int, input().split())
for i in range(M):
    t.append(tuple(input().split(' ')))

df = pd.DataFrame(t, columns=['p', 'S'])
alist = df.groupby('p')['S'].apply(list)

#print(df)
#print(alist)

#print(alist[0])

#print(alist.apply(lambda d: d[:d.index('AC')))

c = 0
NG = 0
for i in range(M):
    try:
        k = alist[i].index('AC')
    except:
        NGtmp = alist[i].count('WA')
        NG = NG + NGtmp
    else:
        NGtmp = alist[:k].count('WA')
        c = c + 1
        NG = NG + NGtmp

print('%s %s'%(c, NG))


### FIXED CODE ###

import sys

readline = sys.stdin.readline

def main():
    N, M = map(int, readline().split())
    aclist = [0] * N
    wrongcount = [0] * N
    for _ in range(M):
        p, S = readline().split()
        q = int(p)-1
        if aclist[q] == 0 and S == 'WA':
            wrongcount[q] += 1
        if S == 'AC':
            aclist[q] = 1

    pena = 0
    for i in range(N):
        if aclist[i] == 1:
            pena += wrongcount[i]
    ac = sum(aclist)

    print(ac, pena)


if __name__ == "__main__":
    main()
max = 0
i = 0
j = 0
k = 0
n_max = 0

n_max = int(raw_input())
price = [1,2,3,4,5,6]

for i in range(6)
    for j in range(j, 6)
        if max <= price[j] - price[i]:
            print max

### FIXED CODE ###

import sys

n = int(raw_input())

min_R = int(raw_input())
nums = map(int, sys.stdin.readlines())

ans = -10**9

for num in nums:
    if num - min_R > ans:
        ans = num - min_R
    if num < min_R:
        min_R = num
        
print ans
N = int(input())
H =list(map(int, input().split()))
count = []
count_tmp = 0
for i in range(N-1):
  if H[i] >= H[i+1]:
    count_tmp += 1
  else:
    count.append(count_tmp)
    count_tmp = 0
print(max(count))
  

### FIXED CODE ###

N = int(input())
H =list(map(int, input().split()))
count = []
count_tmp = 0
if N == 1:
    print(0)
else:
    for i in range(N-1):
        if H[i] >= H[i+1]:
            count_tmp += 1
            if i == N-2:
                count.append(count_tmp)
        else:
            count.append(count_tmp)
            count_tmp = 0
    print(max(count))
from sys import stdin,stdout


n = int(stdin.readline())
dp = [0 for i in range(n)]
a  = list(map(int,stdin.readline().split()))
dp[1] = abs(a[1] - a[0])
if(n>1):
  for i in range(2,n):
  	dp[i] = min(dp[i-1] + abs(a[i]-a[i-1]) + dp[i-2] + abs(a[i]-a[i-2]))
print(dp[-1])


### FIXED CODE ###

from sys import stdin,stdout


n = int(stdin.readline())
dp = [0 for i in range(n)]
a  = list(map(int,stdin.readline().split()))
dp[1] = abs(a[1] - a[0])
if(n>1):
  for i in range(2,n):
  	dp[i] = min(dp[i-1] + abs(a[i]-a[i-1]) , dp[i-2] + abs(a[i]-a[i-2]))
print(dp[-1])
N = int(input())
A = input().split()
answer = 1
flag = 0
x = 10**18
for i in range(N):
  A[i] = int(A[i])
  answer *= A[i]
  if answer == 0:
    break

check = answer/x
if ((check) >= 1) and (answer != x):
  print(-1)
else:
  print(answer)

### FIXED CODE ###

A,B =map(int,input().split())
print(A*B)
import itertools
n, m, q = map(int, input().split())
I = list(range(1, m + 1))
A = list(map(list, itertools.combinations(I, n)))
l = len(A)
for i in range(l):
    if A[0][0] == 1:
        A.append(A[0])
    A.pop(0)
l = len(A)
ans = [0 for i in range(l)]
for _ in range(q):
    a, b, c, d = map(int, input().split())
    for i in range(l):
        if A[i][b - 1] - A[i][a - 1] == c:
            ans[i] += d

print(max(ans))

### FIXED CODE ###

import itertools

n, m, q = map(int, input().split())
I = list(range(1, m + 1))
A = list(map(list, itertools.combinations_with_replacement(I, n)))
l = len(A)
ans = [0 for i in range(l)]
for _ in range(q):
    a, b, c, d = map(int, input().split())
    for i in range(l):
        if A[i][b - 1] - A[i][a - 1] == c:
            ans[i] += d
print(max(ans))
a = list(map(int,input().split()))
a.sort()
for i in range(1,4):
    print(a[-i])

### FIXED CODE ###

a = []
for i in range(10):
    a.append(int(input()))
a.sort()
for j in range(3):
    print(a[-(j+1)])
mod = 10**9+7
def sieve(N):#エラトステネスの篩
    prime = [0]*(N+1)
    isprime = [True]*(N+1)
    isprime[0]=isprime[1] = False
    num = 0
    for p in range(2,N+1):
        if isprime[p]:
            prime[num] = p
            num += 1
            for j in range(2*p,N+1,p):
                isprime[j] = False
    prime.sort()
    prime.reverse()
    for k in range(N-1):
        if prime[k+1] == 0:
            end = k
            break
    return prime[:end+1]

def comb(n,k):
    n1, k = n+1, min(k, n-k)
    numer = denom = 1
    for i in range(1,k+1):
        numer = numer*(n1-i)
        denom = denom*i
    return numer//denom

def solve():
    N,M = map(int,input().split())
    if M == 1:
        print(1)
    prime = sieve(M)
    prime.sort()
    b = {}
    for i in prime:
        if M%i == 0:
            cnt = 0
            while M%i == 0:
                cnt += 1
                M //= i
            b[i] = cnt
    ans = 1
    for num in b:
        ans *= comb(b[num]+N-1,b[num])
        ans %= mod
    print(ans)

if __name__=="__main__":
    solve()

### FIXED CODE ###

mod = 10**9+7
def prime(n,p):
    iteral = 0
    while n%p == 0:
        n //= p
        iteral += 1
    return iteral,n
def modpow(a,n):#二乗
    if n==0:
        return 1
    elif n==1:
        return a%mod
    elif n%2==0:
        return (modpow(a,n/2)**2)%mod
    else:
        return (a*modpow(a,n-1))%mod
def modfact(l,r):#階乗
    fact=1
    for i in range(l-r+1):
        fact=fact*(r+i)%mod
    return fact
def comb(n,x):#組み合わせ
    S=modfact(n,n-x+1)
    fact=modfact(x,1)
    T=modpow(fact,mod-2)
    return S*T%mod
def main():
    N,M = map(int,input().split())
    b = {}
    for i in range(2,int(M**0.5)+10):
        if M%i==0:
            num,M = prime(M,i)
            b[i] = num
    if M > 1:
        b[M] = 1
    ans = 1
    for num in b:
        ans *= comb(b[num]+N-1,b[num])
        ans %= mod
    print(ans)

if __name__ == "__main__":
    main()
import sys
read = sys.stdin.readline


def readln():
    return list(map(int, read().split()))


N, M = readln()
A = [0]*M
B = [0]*M
for i in range(M-1, -1, -1):
    a, b = readln()
    A[i], B[i] = a, b
# AB = [readln() for _ in range(M)]
# A = [ab[0]-1 for ab in AB[::-1]]
# B = [ab[1]-1 for ab in AB[::-1]]


class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        # 親ノードをしめす。負は自身が親ということ。
        self.parent = [-1] * N  # idxが各ノードに対応。

    def root(self, A):
        # print(A)
        # ノード番号を受け取って一番上の親ノードの番号を帰す
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])  # 経由したノードすべての親を上書き
        return self.parent[A]

    def size(self, A):
        # ノード番号を受け取って、そのノードが含まれている集合のサイズを返す。
        return -self.parent[self.root(A)]

    def concat(self, A, B):
        # ノード番号を2つ受け取って、そのノード同士をつなげる処理を行う。
        # 引数のノードを直接つなぐ代わりに、親同士を連結する処理にする。
        A = self.root(A)
        B = self.root(B)

        # すでにくっついている場合
        if (A == B):
            return False

        # 大きい方に小さい方をくっつけたほうが処理が軽いので大小比較
        if (self.size(A) < self.size(B)):
            A, B = B, A

        # くっつける
        self.parent[A] += self.parent[B]  # sizeの更新
        self.parent[B] = A  # self.rootが呼び出されればBにくっついてるノードもすべて親がAだと上書きされる

        return True


ans = [N * (N - 1) // 2]
uni = UnionFind(N)
for a, b in zip(A, B):
    if uni.root(a) == uni.root(b):
        ans.append(ans[-1])
    else:
        ans.append(ans[-1] - uni.size(a) * uni.size(b))
        uni.concat(a, b)

for a in ans[-2::-1]:
    print(a)


### FIXED CODE ###

def readln():
    return list(map(int, input().split()))


N, M = readln()
AB = [readln() for _ in range(M)]
A = [ab[0]-1 for ab in AB[::-1]]
B = [ab[1]-1 for ab in AB[::-1]]


class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        # 親ノードをしめす。負は自身が親ということ。
        self.parent = [-1] * N  # idxが各ノードに対応。

    def root(self, A):
        # print(A)
        # ノード番号を受け取って一番上の親ノードの番号を帰す
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])  # 経由したノードすべての親を上書き
        return self.parent[A]

    def size(self, A):
        # ノード番号を受け取って、そのノードが含まれている集合のサイズを返す。
        return -self.parent[self.root(A)]

    def concat(self, A, B):
        # ノード番号を2つ受け取って、そのノード同士をつなげる処理を行う。
        # 引数のノードを直接つなぐ代わりに、親同士を連結する処理にする。
        A = self.root(A)
        B = self.root(B)

        # すでにくっついている場合
        if (A == B):
            return False

        # 大きい方に小さい方をくっつけたほうが処理が軽いので大小比較
        if (self.size(A) < self.size(B)):
            A, B = B, A

        # くっつける
        self.parent[A] += self.parent[B]  # sizeの更新
        self.parent[B] = A  # self.rootが呼び出されればBにくっついてるノードもすべて親がAだと上書きされる

        return True


ans = [N * (N - 1) // 2]
uni = UnionFind(N)
for a, b in zip(A, B):
    if uni.root(a) == uni.root(b):
        ans.append(ans[-1])
    else:
        ans.append(ans[-1] - uni.size(a) * uni.size(b))
        uni.concat(a, b)

for a in ans[-2::-1]:
    print(a)
import itertools
s=['S','H','C','D']
n=[str(i) for i in range(1,14)]
c=[x+' '+y for x,y in itertools.product(s,n)]
for _ in range(input()):
 c.remove(input())
print(*c)

### FIXED CODE ###

n=int(input())
e=[input()for _ in[0]*n]
for s in"SHCD":
 for r in range(1,14):
  if f'{s} {r}'not in e:print(s,r)
n=input().split()
n=[int(i) for i in n]
h=[]
for i in range(n[0]):
    h.append(int(input()))
h.sort()

q=-1
for i in range(len(h)):
    a=h[i+n[1]-1]-h[i]
    if q==-1 or q>a:
        q=a
    if q==0:
        break
print(q)

### FIXED CODE ###

n=input().split()
n=[int(i) for i in n]
h=[0]*n[0]
for i in range(n[0]):
    h[i]=int(input())
h.sort()
q=-1
for i in range(0,len(h)-n[1]+1):
    a=h[i+n[1]-1]-h[i]
    if q==-1 or q>a:
        q=a
print(q)
N = int(input())
S = list(input())

count = 0

if N >= 3:
    for i in range(N - 1):
        if S[i] == 'A' and S[i + 1] == 'B' and S[i + 2] == 'C':
           count += 1
    print(count)
else:
    print(0)



### FIXED CODE ###

N = int(input())
S = list(input())

count = 0

if N >= 3:
    for i in range(N - 1):
        if (i + 2) < N and S[i] == 'A' and S[i + 1] == 'B' and S[i + 2] == 'C':
           count += 1
    print(count)
else:
    print(0)