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


x=int(input())

def enum_div(n):
    ir=int(n**(0.5))+1
#    ret=[]
    ret=set()
    for i in range(1,ir):
        if n%i == 0:
            ret.add(i)
#            ret.append(i)
            if (i!= 1) & (i*i != n):
#                ret.append(n//i)
                ret.add(n//i)
    return ret

ret=enum_div(x)

y=70000
for ai in range(-y,y):
    yn=""
    for r in ret:
        bi=ai-r
        if ai**5-bi**5==x:
            yn="YES"
            break
        bi=ai+r
        if ai**5-bi**5==x:
            yn="YES"
            break
    if yn=="YES":
        break

if yn=="YES":
    print(ai,bi)


### FIXED CODE ###


x=int(input())

def enum_div(n):
    ir=int(n**(0.5))+1
#    ret=[]
    ret=set()
    for i in range(1,ir):
        if n%i == 0:
            ret.add(i)
#            ret.append(i)
            if (i!= 1) & (i*i != n):
#                ret.append(n//i)
                ret.add(n//i)
    return ret

ret=enum_div(x)

y=20000
for ai in range(-y,y):
    yn=""
    for r in ret:
        bi=ai-r
        if ai**5-bi**5==x:
            yn="YES"
            break
        bi=ai+r
        if ai**5-bi**5==x:
            yn="YES"
            break
    if yn=="YES":
        break

if yn=="YES":
    print(ai,bi)
### BUGGY CODE ###

import sys


def main():
    input = sys.stdin.readline
    N, T = map(int, input().strip().split())
    foods = [list(map(int, input().strip().split())) for _ in range(N)]

    ans = 0
    before_dp = [[0] * T for _ in range(N)]
    for i, food in enumerate(foods):
        now_foods = foods[:i] + foods[i+1:]
        dp = before_dp[:i] + [[0] * T for _ in range(N-i)]
        for j, n_food in enumerate(now_foods):
            if j < i-1:
                continue
            n_a, n_b = n_food
            for k in range(T):
                if k < n_a:
                    dp[j+1][k] = dp[j][k]
                else:
                    dp[j+1][k] = max(dp[j][k], dp[j][k-n_a]+n_b)
        #print(dp[j+1])
        ans = max(ans, dp[-1][-1]+food[1])
        before_dp = dp
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from operator import itemgetter


def main():
    input = sys.stdin.readline
    N, T = map(int, input().strip().split())
    foods = sorted([list(map(int, input().strip().split())) for _ in range(N)], key=itemgetter(0))

    ans = 0
    dp = [[0] * (T+1) for _ in range(N+1)]
    for j, food in enumerate(foods):
        n_a, n_b = food
        for k in range(T+1):
            if k == T:
                dp[j+1][k] = max(dp[j][k], dp[j][k-1]+n_b)
            elif k < n_a:
                dp[j+1][k] = dp[j][k]
            else:
                dp[j+1][k] = max(dp[j][k], dp[j][k-n_a]+n_b)
        #print(dp[j+1])
    ans = dp[-1][-1]
    print(ans)

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

n=int(input())
a=list(map(int,input().split()))
b=0
c=[0]*n
for i in range(n):
    c[i] = str(a.index(i+1)+1)
print(" ".join(c))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
l = []
for i in range(n):
    l.append((a[i], i+1)) 
c = sorted(l)
for i in range(n):
    print(c[i][1])
### BUGGY CODE ###

n1, n2 = [int(i) for i in input().split()]
n3 = [int(i) for i in input().split()]

n3.sort(reverse = True)
n4 = []
for i1 in range(n2):
    if i1 != 0:
        if len(n3) == 0:
            n4[0] = n4[0] // 2
        elif n3[0] <= n4[0]:
            n4[0] = n4[0] // 2
        else:
            n4.append(n3[0] // 2)
            n3 = n3[1:len(n3)]
        n4.sort(reverse = True)
    else:
        n4.append(n3[0] // 2)
        n3 = n3[1:len(n3)]

r1 = 0
for i2 in range(len(n3)):
    r1 += n3[i2]
for i3 in range(len(n4)):
    r1 += n4[i3]

print(r1)

### FIXED CODE ###

n1, n2 = [int(i) for i in input().split()]
n3 = [int(i) for i in input().split()]

n3.sort(reverse = True)

c1 = 0
while True:
    n3[0] = n3[0] // 2
    c1 += 1
    if c1 >= n2:
        break
    t2 = 1
    while len(n3) != 1:
        if n3[t2] >= n3[0]:
            n3[t2] = n3[t2] // 2
            t2 += 1
            c1 += 1
            if c1 >= n2 or t2 >= len(n3):
                break
        else:
            break

    if c1 >= n2:
        break

    n3.sort(reverse = True)

r1 = 0
for i2 in range(n1):
    r1 += n3[i2]

print(r1)
### BUGGY CODE ###

import collections
n=int(input())
s=input()
ans=0
d=collections.defaultdict(int)
for i in range(n):
  t=0
  for j in range(i,n):
    t+=(ord(s[j])-96)*(100**(j-i))
    if 0<d[t]<i and j-i+1>ans:
      ans=j-i+1
    elif d[t]==0 and i+2*(j-i+1)<=n:
      d[t]=j
    
print(ans)


### FIXED CODE ###

import collections
mod=10**9+7
base=257
n=int(input())
S=list(ord(s)-96 for s in input())
B=[0]*(n+1)
B[0]=1
for i in range(n):
  B[i+1]=(B[i]*base)%mod

def chk(x):
  ret=False
  h=0
  bx=B[x]
  d=collections.defaultdict(int)
  for i in range(x):
    h=(h*base+S[i])%mod
  d[h]=x
  for i in range(x,n):
    h=(h*base+S[i]-S[i-x]*bx)%mod
    if d[h]==0:
      d[h]=i+1
    elif d[h]<=i-x+1:
      ret=True
  return ret

l,r=0,n//2
while r-l>1:
  m=(l+r)//2
  if chk(m):
    l=m
  else:
    r=m
print(r if chk(r) else l)
### BUGGY CODE ###

N=int(input())
L=input()
L=L.split()
L=[int(item) for item in L]
L.sort()

ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if (L[i]+L[j])>L[k]:
                ans+=1

print(ans)

### FIXED CODE ###

from operator import mul
from functools import reduce
import bisect

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N=int(input())
L=input()
L=L.split()
L=[int(item) for item in L]
L.sort()
ans=cmb(N,3)
ans2=0
for i in reversed(range(2,N)):
    for j in reversed(range(1,i)):
        a=bisect.bisect_right(L,L[i]-L[j])
#        print('{0}:{1}'.format(a,j))
#        print(a)
        if(a<j):
            ans2+=(j-a)
    

print(ans2)
### BUGGY CODE ###

import math

N = int(input())
a = list(map(int,input().split()))
a_odds = []
a_even = []

for i in range(N):
    if a[i]%2 != 0:
        a_odds.append(a[i])
    else:
        a_even.append(a[i])

a_odds.sort()
a_odds.reverse()
a_even.sort()
a_even.reverse()

count = 0
alist = []
num= 0
if a_odds!=[] and a_even!=[]:
    num = max(a_odds[0],a_even[0])
elif a_odds ==[]:
    num= a_even[0]
elif a_even == []:
    num = a_odds[0]
    
for i in range(math.floor(math.log2(num))+1,0,-1):
    alist.append(2**i)


while(a_odds!=[]):
    temp = a_odds[0]
    a_odds.pop(0)
    b=2**math.floor(math.log2(temp))
    if a_odds ==[]:
        break
    if 2*b-temp in a_odds:
        count += 1
        a_odds.pop(a_odds.index(2*b-temp))
    
    
while(a_even!=[]):
    temp = a_even[0]
    a_even.pop(0)
    if a_even==[]:
        break
    for i in alist:
        if temp > i:
            break
        if (i-temp) in a_even:
            count += 1
            a_even.pop(a_even.index(i-temp))
            break
    

print(count)







### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
b = {}
for i in range(len(a)):
    if a[i] in b:
        b[a[i]] += 1
    else:
        b[a[i]] = 1
twins = []
now = 1
while now <= a[-1]:
    now *= 2
    twins.append(now)
for i in range(len(a) - 1, -1, -1):
    tmpa = 0
    if  b[a[i]] == 0:
        continue
    for j in range(len(twins) - 1, -1, -1):
        if twins[j] <= a[i]:
            break
        tmpa = twins[j] - a[i]
    if tmpa == a[i]:
        if b[tmpa] >= 2:
            b[tmpa] -= 2
    elif tmpa in b and b[tmpa] != 0:
        b[tmpa] -= 1
        b[a[i]] -= 1
countb = 0
for i in b:
    countb += b[i]
print((n - countb) // 2)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
for i in range(n):
    print(c[i+1])
### BUGGY CODE ###

N,M=map(int,input().split())
ps=[list(input().split()) for _ in range(M)]

a=[]
w=[]
count=0

for j in range(M):
    if ps[j][1]=="WA":
        if ps[j][0] not in a:
            w.append(ps[j][0])
    elif ps[j][1]=="AC":
        if ps[j][0] not in a:
            a.append(ps[j][0])
            count+=w.count(ps[j][0])


print(len(a),count)

### FIXED CODE ###

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

AC=[0]*N
WA=[0]*N
ac=0
wa=0

for i in range(M):
    p,s=map(str,input().split())
    P=int(p)
    if s=="AC":
        if AC[P-1]!=P:
            AC[P-1]+=P
            ac+=1
            wa+=WA[P-1]
    else:
        if AC[P-1]!=P:
            WA[P-1]+=1

print(ac,wa)
### BUGGY CODE ###

from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline

def main():
    n=int(input())
    d=defaultdict(deque)
    for i in range(n):
        d[i+1]=deque(map(int,input().split()))

    c=0
    immortalskip=set()
    while any(d.values()):
        c+=1
        f=0
        skip=set()
        for i in range(1,n+1):
            if i not in skip.copy() and i not in immortalskip:
                if d[i]:
                    if d[i][0] in skip:
                        continue
                    elif i==d[d[i][0]][0]:
                        oppo=d[i].popleft()
                        d[oppo].popleft()
                        skip.add(oppo)
                        skip.add(i)
                        f=1
                else:
                    immortalskip.add(i)
#            print(c,i,d,skip,f)
        if not f:
            print(-1)
            exit()

    print(c)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline
import time
t=time.time()

def main():
    n=int(input())
    d=[[]]+[deque(map(int,input().split()))for i in n*[0]]

    c=0
    while any(d):
        c+=1
        f=0
        skip=set()
        for i in range(1,n+1):
            if i not in skip:
                if d[i]:
                    if d[i][0] in skip:
                        continue
                    elif i==d[d[i][0]][0]:
                        oppo=d[i].popleft()
                        d[oppo].popleft()
                        skip.add(oppo)
                        skip.add(i)
                        f=1

        if not f:
            print(-1)
            exit()
        if abs(time.time()-t)>1:
            print(n*(n-1)//2)
            exit()

    print(c)

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

N=int(input())
a=list(map(int,input().split()))
A=[0]*N
B=[]
count=0
for i in range(N)[::-1]:
    asum=0
    x=i+1
    for j in range(i,N,x):
        asum=asum+A[j]
    if asum%2==a[i]:
        A[i]=0
    else:
        A[i]=1
        B.insert(0,i+1)
        count=count+1
print(count)
if count!=0:
    print(*B)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
A=[0]*N
B=[]
for i in range(N//2,N):
    if a[i]==1:
        A[i]=1
        B.append(i+1)
for i in range(N//2)[::-1]:
    asum=0 
    x=i+1
    for j in range(i,N,x):
        asum=asum+A[j]
    if asum%2!=a[i]:
        A[i]=1
        B.append(i+1)
count=sum(A)
print(count)
if count!=0:
    print(*B)
### BUGGY CODE ###

import itertools
N,K=map(int,input().split())
L=[]
for l in range(N):
  L.append(int(input()))
R=list(itertools.combinations(L,K))
ans=[]
for r in R:
  ans.append(max(r)-min(r))
print(min(ans))

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for i in range(N)]
h.sort()
ans=[]
for i in range(len(h)-K+1):
  b=h[K+i-1]-h[i]
  ans.append(b)
print(min(ans))
### BUGGY CODE ###

import collections

n = int(input())
ln = list(map(int, input().split()))
m = int(input())
lm = list(map(int, input().split()))

c = collections.Counter(lm)

for i in range(len(c)):
    if ln.count(list(c.keys())[i]) < c[list(c.keys())[i]]:
        print("NO")
        exit()

print("YES")

### FIXED CODE ###

import sys
from collections import Counter
 
N = int(input())
s1 = list(map(int,input().split()))
M = int(input())
s2 = list(map(int,input().split()))
 
c1 = Counter(s1)
c2 = Counter(s2)
 
for k,v in c2.items():
    if k in c1:
        if v > c1[k]:
            print('NO')
            sys.exit()
    else:
        print('NO')
        sys.exit()
print('YES')
### BUGGY CODE ###

import sys
stdin=sys.stdin

ns=lambda:input().rstrip()
ni=lambda:int(input().rstrip())
nm=lambda:map(int,input().split())
nl=lambda:list(map(int,input().split()))

N,Q=nm()
AB=[nl() for i in range(N-1)]
PQ=[nl() for i in range(Q)]
root=[[] for i in range(N)]
N_val=[0]*N
ans_val=[0]*N
d=[0]*N

def dfs(x,d,s):
  for i in root[x]:
    if(d[i]==0):
      s+=N_val[i]
      ans_val[i]=s
      d[i]=1
      dfs(i,d,s)
      s-=N_val[i]
      

for i in range(N-1):
  root[AB[i][0]-1]+=[AB[i][1]-1]
  root[AB[i][1]-1]+=[AB[i][0]-1]
  
for i in range(Q):
  N_val[PQ[i][0]-1]+=PQ[i][1]

  
ans_val[0]=N_val[0]
d[0]=1
dfs(0,d,N_val[0])
print(*ans_val)

### FIXED CODE ###

import sys
from collections import deque
stdin=sys.stdin

ns=lambda:input().rstrip()
ni=lambda:int(input().rstrip())
nm=lambda:map(int,input().split())
nl=lambda:list(map(int,input().split()))

N,Q=nm()
AB=[nl() for i in range(N-1)]
PQ=[nl() for i in range(Q)]
root=[[] for i in range(N)]
N_val=[0]*N
ans_val=[0]*N
d=[0]*N

def bfs():
  que=deque([])
  que.append(0)
  while que:
    p=que.popleft()
    for i in root[p]:
       if(d[i]==0):
         ans_val[i]=ans_val[p]+N_val[i]
         que.append(i)
         d[i]=1
      
def dfs(x,d,s):
  for i in root[x]:
    if(d[i]==0):
      s+=N_val[i]
      ans_val[i]=s
      d[i]=1
      dfs(i,d,s)
      s-=N_val[i]
      

for i in range(N-1):
  root[AB[i][0]-1]+=[AB[i][1]-1]
  root[AB[i][1]-1]+=[AB[i][0]-1]
  
for i in range(Q):
  N_val[PQ[i][0]-1]+=PQ[i][1]

  
ans_val[0]=N_val[0]
d[0]=1
#dfs(0,d,N_val[0])
bfs()
print(*ans_val)
### BUGGY CODE ###

k, s = map(int, input().split())
n = 0
for i in range(k + 1):
    if (s-i)/2 > k:
        continue
    elif i > s:
        break
    for j in range(k + 1):
        if s-i-j > k:
            continue
        elif j > s:
            break
        for l in range(k + 1):
            if i + j + l == s:
                n += 1
            elif i + j + l > s:
                break
print(n)


### FIXED CODE ###

k, s = map(int, input().split())
n = 0
for i in range(k + 1):
    if (s-i)/2 > k:
        continue
    elif i > s:
        break
    for j in range(k+1):
        z = s - i - j
        if 0<= z <= k:
            n += 1
print(n)
### BUGGY CODE ###

S = list(map(int,input().split()))
N = S[0]
X = S[1]
x = list(map(int,input().split()))
n = max(max(x),X)//N 

for i in range(n,0,-1):
    xmod = list()
    xmod.append(X % i)
    for y in range(0,N):
        xmod.append(x[y] % i)
    if xmod.count(xmod[0]) == len(xmod):
        print(i)
        break

### FIXED CODE ###

import fractions
from functools import reduce

S = list(map(int,input().split()))
N = S[0]
X = S[1]
x = list(map(int,input().split()))
x.append(X)
xmin = min(x)
xlist = list(map(lambda y: y-xmin ,x))
xlist.remove(0)

answer = reduce(fractions.gcd, xlist)
print(answer)
### BUGGY CODE ###

import numpy as np

n = int(input())
a = list(map(int, input().split()))
sum = 0
for i in range(len(a)-1):
    for j in range(i+1,len(a)):
        sum += a[i]*a[j]
        
ans = np.mod(sum,10**9+7)

print(ans)

### FIXED CODE ###


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

MOD = 10 ** 9 + 7

sum = sum(a) % MOD
ans = 0

for i in range(len(a)):
    sum -= a[i]
    sum %= MOD
    ans += a[i] * sum
    ans %= MOD

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

from copy import deepcopy
import numpy as np
def factor(N):
    ans = []
    for i in range(1,int(np.sqrt(N))+1):
        if N%i == 0:
            ans.append(i)
    for i in range(len(ans)):
        ans.append(N//ans[i])
    ans = list(set(sorted(ans)))
    return ans

def check(K,N):
    while 1:
        if N%K == 0:
            N = N//K
        else:
            break
    if N%K == 1:
        return True
    else:
        return False

N = int(input())
ans = len(factor(N-1)[1:])
for K in factor(N)[1:]:
    if check(K,N):
        ans += 1

print(ans)    

### FIXED CODE ###

import numpy as np
def factor(N):
    ans = []
    for i in range(1,int(np.sqrt(N))+1):
        if N%i == 0:
            ans.append(i)
            if N//i != i:
                ans.append(N//i)
    return ans

def check(K,N):
    while N >= K:
        if N%K == 0:
            N //= K
        else:
            N %= K
    if N%K == 1:
        return True
    else:
        return False

N = int(input())
ans = len(factor(N-1))-1

for K in factor(N)[1:]:
    if check(K,N):
        ans += 1

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

import sys
 
stdin = sys.stdin

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

check_point = []
inf = 10 ** 18

# AC文字列のAの位置をリストに収めた
for i in range(inf):
  out = S.find('AC')
  if out < 0:
    break
  else:
    S = S[out+2:]
    check_point.extend([(out + len(check_point) * 2)])
  

# 指定した文字列範囲を含む要素数を表示
for i in range(Q):
  start, end  = map(int, stdin.readline().split())
  print(len([i for i in check_point if (start - 1 <= i) and (i + 1 < end)]))


### FIXED CODE ###

import sys
 
stdin = sys.stdin

N,Q = map(int,input().split())
S = input()
se = [list(map(int, stdin.readline().split())) for i in range(Q)]

list_out = [0] * N
cnt = 0
f = 0

# AC文字列のAの位置をリストに収めた
for i in range(len(S)):
  if S[i] == 'A':
    f = 1
    list_out[i] = list_out[i-1]    
  elif S[i] == 'C':
    if f == 1:
      cnt += 1
      f = 0
      list_out[i] = cnt
    else:
      list_out[i] = list_out[i-1]
  else:
    f = 0
    list_out[i] = list_out[i-1]    


# 指定した文字列範囲を含む要素数を表示
for i in se:
  print(list_out[i[1]-1] - list_out[i[0]-1])
### BUGGY CODE ###

import sys
N,K = map(int,input().split())
H = list(map(int,input().split()))
if N-K <= 0:
    print(0)
    sys.exit()
for i in range(N-(N-K)):
    H.remove(max(H))
print(sum(H))

### FIXED CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
H.sort(reverse=True)
a = 0
for i in range(K,N):
    a += H[i]
print(a)
### BUGGY CODE ###

import sys
import copy
n, m = map(int, input().split())
keys = []
box = [[] for _ in range(n+1)]
for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    c = list(map(int, sys.stdin.readline().split()))
    keys.append([a, b, c])
    for j in c:
        box[j].append(i)


def deta(n, remain, price):
    if len(remain) == 0:
        return price
    res = -1
    r = copy.copy(remain)
    b = remain.pop()
    for k in box[b]:
        bn = copy.copy(remain)
        for nb in keys[k][2]:
            if nb in bn:
                bn.remove(nb)
        p = deta(n, bn, price + keys[k][0])
        if res == -1 or p < res:
            res = p
    return res

rem = set(range(1, n+1))
result = deta(n, rem, 0)
print(result)

### FIXED CODE ###

import sys
n, m = map(int, input().split())
keys = []
box = [[] for _ in range(n+1)]

dr = 2**n
dp = [-1] * dr
dp[0] = 0

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    c = list(map(int, sys.stdin.readline().split()))
    k = 0
    for box in c:
        k += 1 << box-1
    for j in range(dr):
        if dp[j] != -1:
            price = dp[j] + a
            nex = j | k
            if dp [nex] == -1 or dp[nex] > price:
                dp[nex] = price

print(dp[dr-1])
### BUGGY CODE ###

import math
from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}

    def make(self, x):
        self.p[x] = x

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if x >= y:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            return x


_ncr = {}


def ncr(n, r):
    if n < r:
        return 0
    k = "{}:{}".format(n, r)
    if k not in _ncr:
        _ncr[k] = math.factorial(n) // (math.factorial(n - r) *
                                        math.factorial(r))
    return _ncr[k]


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = ncr(N, 2)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += ncr(nx, 2) + ncr(ny, 2)
        total -= ncr(n, 2)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)

### FIXED CODE ###

from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def nc2(n):
    return (n * (n - 1)) >> 1


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = nc2(N)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += nc2(nx) + nc2(ny)
        total -= nc2(n)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
temp = []

for i in range(n):
    # print(i, p[i])
    if p[i] == i+1:
        temp.append('y')
        continue

    # if p[i] == i+1:
    #     if p[i-1] == i:
    #         del temp[-1]
    #         temp.append('x')
    #     else:
    #         temp.append('y')
    #     continue

    temp.append(p[i])

idx = 1
while True:
    if idx > len(temp) - 1:
        break

    if temp[idx] == 'y' and temp[idx-1] == 'y':
        temp[idx-1] = 'x'
        del temp[idx]
        # del temp[idx-1]
        # temp.append('x')

    idx += 1


#print(temp)
ans = temp.count('x') + temp.count('y')
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
temp = []

for i in range(n):
    # print(i, p[i])
    if p[i] == i+1:
        temp.append('y')
        continue

    temp.append(p[i])

a = []

idx = 1
while True:
    if idx > len(temp) - 1:
        break

    if temp[idx] == 'y' and temp[idx-1] == 'y':
        temp[idx-1] = 'x'
        temp[idx] = 'x'
        #del temp[idx]
        # del temp[idx-1]
        # temp.append('x')

    idx += 1


#print(a)
ans = temp.count('x')//2 + temp.count('y')
print(ans)


'''
9
1 2 4 9 5 8 7 3 6
'''