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

def main():
    s = list(input())
    k = int(input())
    lens = len(s)
    subs = []
    for i1 in range(1, lens + 1):
        for i2 in range(0, lens +1 - i1):
            subs.append(tuple(s[i2:i1+i2]))
    subs = set(subs)
    subs = list(subs)
    subs.sort()
    r = subs[k-1]
    print("".join(r))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    s = list(input())
    k = int(input())
    k -= 1

    d1 = defaultdict(list)
    for i, c in enumerate(s):
        d1[c].append(i)
    d2 = sorted(d1.items())

    lens = len(s)
    for d2e in d2:
        subs = set()
        subs.add(d2e[0])
        for d2ee in d2e[1]:
            end = min(lens + 1, d2ee + k + 2)
            for i1 in range(d2ee+1, end):
                subs.add("".join(s[d2ee:i1]))
        if len(subs) > k:
            subsl = list(subs)
            subsl.sort()
            print(subsl[k])
            sys.exit()
        else:
            k -= len(subs)

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

N = int(input())
a = sorted(list(map(int, input().split())))
import numpy as np
from scipy.misc import comb

def find_p(n, i):
    lo = 0
    hi = i
    mid = (hi-lo)//2
    xl = a[0]
    xh = a[i]
    while hi - lo > 1:
        mid = (hi+lo)//2
        if a[mid] > n//2:
            hi = mid
        else:
            lo = mid
    if abs(a[lo] - n/2) > abs(a[hi] - n/2):
        return a[hi]
    else:
        return a[lo]

ans = (0, 0)
x = 0
for j in range(N):
    i = N-j-1
    n = a[i]
    p = find_p(n, i)
    y = comb(n, p)
    if y > x:
        ans = (n, p)
        x = y

print(str(ans[0]) + ' ' + str(ans[1]))

### FIXED CODE ###

N = int(input())
a = sorted(list(map(int, input().split())))

def find_p(n, i):
    lo = 0
    hi = i
    mid = (hi-lo)//2
    xl = a[0]
    xh = a[i]
    while hi - lo > 1:
        mid = (hi+lo)//2
        if a[mid] > n//2:
            hi = mid
        else:
            lo = mid
    if abs(a[lo] - n/2) > abs(a[hi] - n/2):
        return a[hi]
    else:
        return a[lo]



print(str(a[-1]) + ' ' + str(find_p(a[-1], N-1)))
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
rows = [input() for i in range(H)]
cols = []
for i in range(W):
    col = ''
    for row in rows:
        col += row[i]
    cols.append(col)

def create_light_list(tdl, reverse):
    ret = []
    lenl = len(tdl[0])
    tl = range(lenl)[::-1] if reverse else range(lenl)
    for l in tdl:
        d = deque()
        cur = 0
        for i in tl:
            if l[i] == '#':
                cur = 0
            else:
                cur += 1
            if reverse:
                d.appendleft(cur)
            else:
                d.append(cur)
        ret.append(d)
    return ret

# 上下左右の照らされる数だけをあらかじめ計算
L = create_light_list(rows, False)
R = create_light_list(rows, True)
U = create_light_list(cols, False)
D = create_light_list(cols, True)

ans = 0
for i in range(H):
    for j in range(W):
        light = L[i][j] + R[i][j] + U[j][i] + D[j][i] - 3
        ans = max(ans, light)

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]
L, R, U, D = [[[0]*W for _ in range(H)] for i in range(4)]

for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            L[h][w] = L[h][w-1]+1
            U[h][w] = U[h-1][w]+1
        if S[h][W-1-w] == '.':
            R[h][-w-1] = R[h][-w]+1
        if S[H-1-h][w] == '.':
            D[-h-1][w] = D[-h][w]+1

ans = 0
for i in range(H):
    for j in range(W):
        light = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        ans = max(ans, light)

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

N=int(input())
X=input()
def popcount(n):
    s=str(bin(n))
    return len([i for i in s if i=='1'])
def f(n):
    c=0
    while n!=0:
        n=n%popcount(n)
        c=c+1
    return c
for i in range(N):
    F=list(X)
    if F[i]=='1':
        F[i]='0'
    else:
        F[i]='1'
    s=''
    for d in F:
        s=s+d
    print(f(int(s,2)))

### FIXED CODE ###

N=int(input())
X=input()
def popcount(n):
    s=str(bin(n))
    return len([i for i in s if i=='1'])
def f(n):
    c=1
    while n!=0:
        n=n%popcount(n)
        c=c+1
    return c
x=int(X,2)
P=popcount(x)
F=list(X)
L=[1,2]# L[i]=2**i%(P+1)
M=[1,2]# M[i]=2**i%(P-1)
if P!=1:
    for i in range(1,N):
        L.append((L[i]*2)%(P+1))
        M.append((M[i]*2)%(P-1))
    s=x%(P+1)
    t=x%(P-1)
    for i in range(N):
        if F[i] == '1':
            q = (t - M[N-i-1])%(P-1)
            print(f(q))
        else:
            Q = P + 1
            q = (s + L[N-i-1])%(P+1)
            print(f(q))
else:
    for i in range(1,N):
        L.append(0)
    s=x%2
    for i in range(N):
        if F[i] == '1':
            print(0)
        else:
            q = (s + L[N - i - 1])%2
            print(f(q))
### BUGGY CODE ###

p = int(input())
a = [int(item) for item in input().split()]

fac = [1] + [0] * (p - 1)
facinv = [1] + [0] * (p - 1)
for i in range(1, p):
    fac[i] = fac[i-1] * i % p
    facinv[i] = facinv[i-1] * pow(i, p-2, p) % p

# print(fac)
# print(facinv)
comb = [0] * p
for i in range(p):
    comb[i] = fac[p-1] * facinv[i] * facinv[p-1-i] % p

# print(comb)
ans = [0] * p
ppowp = [[0] * (p + 1) for _ in range(p + 1)]
for i in range(p+1):
    val = 1
    for j in range(p+1):
        ppowp[i][j] = val
        val *= i
        val %= p

for i, item in enumerate(a):
    if item == 1:
        ans[0] += 1
        # Calc (i - x)**(p - 1) 
        for j in range(p):
            # ans[j] -= pow(i, p-1-j, p) * pow(-1, j, p) * comb[j] % p
            if j % 2 == 1:
                ans[j] -= ppowp[i][p-1-j] * -1 * comb[j] % p
            else:
                ans[j] -= ppowp[i][p-1-j] * comb[j] % p
            ans[j] %= p
print(" ".join([str(item) for item in ans]))

### FIXED CODE ###

p = int(input())
a = [int(item) for item in input().split()]

fac = [1] + [0] * (p - 1)
facinv = [1] + [0] * (p - 1)
for i in range(1, p):
    fac[i] = fac[i-1] * i % p
    facinv[i] = facinv[i-1] * pow(i, p-2, p) % p

# print(fac)
# print(facinv)
comb = [0] * p
for i in range(p):
    comb[i] = fac[p-1] * facinv[i] * facinv[p-1-i] % p

# print(comb)
ans = [0] * p
ppowp = [[0] * (p + 1) for _ in range(p + 1)]
for i in range(p+1):
    val = 1
    for j in range(p+1):
        ppowp[i][j] = val
        val *= i
        val %= p

for i, item in enumerate(a):
    if item == 1:
        ans[0] += 1
        # Calc (i - x)**(p - 1) 
        for j in range(p):
            # ans[j] -= pow(i, p-1-j, p) * pow(-1, j, p) * comb[j] % p
            if j % 2 == 1:
                ans[j] -= ppowp[i][p-1-j] * -1 * comb[j] % p
            else:
                ans[j] -= ppowp[i][p-1-j] * comb[j] % p
            ans[j] %= p
print(" ".join([str(item) for item in ans]))
### BUGGY CODE ###

n=int(input())
s=sorted(list(map(int,input().split())))
m=int(input())
t=sorted(list(map(int,input().split())))
for i in s:
    if i in t:
        t.remove(i)
if t==[]:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

from collections import Counter
input()
s=list(input().split())
s=Counter(s)
input()
for i in input().split():
    if s.get(i,0)==0:
        print("NO")
        break
    else:
        s[i]-=1
else:
    print("YES")
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
for i in range(N):
    a = A.count(i + 1)
    print(A.count(i + 1))
    A = A[a:]

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [0] * (N - 1)
for i in range(N - 1):
    B[A[i] - 1] += 1
for i in B:
    print(i)
print("0")
### BUGGY CODE ###

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

for i in a:
  ans*=i
  
if ans>10**18:
  print("-1")
else:
  print(str(ans))

### FIXED CODE ###

n=int(input())
a=input().split()
ans=1

if "0" in a:
  print("0")
  exit()
  
for i in range(n):
  ans*=int(a[i])
  if ans>10**18:
    print("-1")
    exit()
  

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

class Unionfind():
    def __init__(self, progsize):
        self.table = [-1 for _ in range(progsize)]
        self.size = [1 for _ in range(progsize)]

    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x

    def union(self, x, y):
        xl = self.find(x)
        yl = self.find(y)
        if xl != yl:
            if self.table[xl] <= self.table[yl]:
                self.table[yl] = xl
                self.table[xl] -= 1
                self.size[xl] += self.size[yl]
            else:
                self.table[xl] = yl
                self.table[yl] -= 1
                self.size[yl] += self.size[xl]

n, m = [int(x) for x in input().split()]
b =  [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
b.reverse()
r = []
t = n*(n-1)//2
ds = Unionfind(n)
for q, p in b:
  r.insert(0, t)
  qq, pp = ds.find(p), ds.find(q)
  if pp != qq:
    t -= ds.size[pp] * ds.size[qq]
  ds.union(p, q)
for x in r:
  print(x)

### FIXED CODE ###

class Unionfind():
    def __init__(self, progsize):
        self.table = [-1 for _ in range(progsize)]
        self.size = [1 for _ in range(progsize)]

    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x

    def union(self, x, y):
        xl = self.find(x)
        yl = self.find(y)
        if xl != yl:
            if self.table[xl] <= self.table[yl]:
                self.table[yl] = xl
                self.table[xl] -= 1
                self.size[xl] += self.size[yl]
            else:
                self.table[xl] = yl
                self.table[yl] -= 1
                self.size[yl] += self.size[xl]

n, m = map(int, input().split())
bridge = [tuple(map(int, input().split())) for _ in range(m)]
bridge.reverse()
uf = Unionfind(n)
cur = n * (n-1) // 2
ans = [cur]
for a, b in bridge:
    ap = uf.find(a-1)
    bp = uf.find(b-1)
    if ap != bp:
        cur -= uf.size[ap] * uf.size[bp]
    uf.union(a-1, b-1)
    ans.append(cur)
for a in reversed(ans[0:m]):
    print(a)
### BUGGY CODE ###

import numpy as np
import copy
N=int(input())
l=list(map(int, input().split()))  #リスト入力
cp = copy.copy(l)
 
if l[0]!=0:

  for k in range(1,N):
    if sum(l[:k])*sum(l[:k+1])>0:
      l[k]=-np.sign(sum(l[:k]))-sum(l[:k])

  if sum(l)==0:
    print(1+sum([abs(l[n]-cp[n]) for n in range(N)]))
  else:
    print(sum([abs(l[n]-cp[n]) for n in range(N)]))
  exit()
  
else:
  #1
  sei_l=copy.copy(l)
  sei_l[0]=1
  for k in range(1,N):

    if sum(sei_l[:k])*sum(sei_l[:k+1])>0:

      sei_l[k]=-np.sign(sum(sei_l[:k]))-sum(sei_l[:k])

  if sum(sei_l)==0:
    c1=1+sum([abs(sei_l[n]-cp[n]) for n in range(N)])
  else:
    c1=sum([abs(sei_l[n]-cp[n]) for n in range(N)])  
  #-1
  fu_l=copy.copy(l)
  sei_l[0]=-1
  for k in range(1,N):

    if sum(fu_l[:k])*sum(fu_l[:k+1])>0:

      fu_l[k]=-np.sign(sum(fu_l[:k]))-sum(fu_l[:k])

  if sum(fu_l)==0:
    c2=1+sum([abs(fu_l[n]-cp[n]) for n in range(N)])
  else:
    c2=sum([abs(fu_l[n]-cp[n]) for n in range(N)])  
  
  print(max(c1,c2))

### FIXED CODE ###

from copy import copy
n = int(input())
a = [int(x) for x in input().split()]
ans1=[(-1)**i for i in range(n)]

b=copy(a)
res_b=0
sb=0
c=copy(a)
res_c=0
sc=0
for i in range(n):
  sb+=a[i]
  if ans1[i]*sb>0:
    pass
  else:
    b[i]=ans1[i]-(sb-b[i])
    sb=sb-a[i]+b[i]
    res_b+=abs(b[i]-a[i])

  sc+=a[i]
  if -1*ans1[i]*sc>0:
    pass
  else:
    c[i]=-1*ans1[i]-(sc-c[i])
    sc=sc-a[i]+c[i]
    res_c+=abs(c[i]-a[i])
  
print(min(res_b,res_c))
### BUGGY CODE ###

import numpy as np
import copy

n = int(input())
c = np.zeros((n-1), dtype=np.int)
s = np.zeros((n-1), dtype=np.int)
f = np.zeros((n-1), dtype=np.int)
for i in range(n-1):
    c[i], s[i], f[i] = map(int, input().split(" "))

t = np.zeros(n, dtype=np.int)
for i in range(n-1):
    w = np.zeros((n-1), dtype=np.int)
    w = copy.deepcopy(s)
    t[i] = s[i] + c[i]
    for j in range((i+1), (n-1), 1):
        k = 0
        while(True):
            if(w[j] >= t[i]):
                t[i] = w[j]
                break
            while(w[j] < t[i]):
                w[j] += f[j]
        t[i] += c[j]

for i in range(n):
    print(t[i])

### FIXED CODE ###

import numpy as np
import copy

n = int(input())
c = np.zeros((n-1), dtype=np.int)
s = np.zeros((n-1), dtype=np.int)
f = np.zeros((n-1), dtype=np.int)
for i in range(n-1):
    c[i], s[i], f[i] = map(int, input().split(" "))

t = np.zeros(n, dtype=np.int)
for i in range(n-1):
    t[i] = s[i] + c[i]
    for j in range((i+1), (n-1), 1):
        if(s[j] >= t[i]):
            t[i] = s[j]
        elif(t[i] % f[j] != 0):
            t[i] += f[j] - (t[i] % f[j])
        t[i] += c[j]

for i in range(n):
    print(t[i])
### BUGGY CODE ###

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

count = 0
for i in range(A, B+1):
  if i % C != 0 and i % D != 0:
    count += 1
print(count)

### FIXED CODE ###

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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

C_ok = (B // C) - ((A-1) // C) 
D_ok = (B // D) - ((A-1) // D)
C_D_ok = (B // lcm(C, D)) - ((A-1) // lcm(C, D))
print((B-A+1)-C_ok-D_ok+C_D_ok)
### BUGGY CODE ###

import math
n = int(input())
a = list()
for i in range(n):
    b = list(input())
    b.sort()
    a.append("".join(b))
# for i in range(n):
#     a.append(input())
# for i, youso in enumerate(a):
#     b = list()
#     for j in youso:
#         b.append(j)
#     b.sort()
#     x = str()
#     for j in b:
#         x += j
#         a[i] = x
x = 0

#TLE ver.
# for i, youso in enumerate(a):
#     for j in range(i, n-1):
#         if youso == a[j+1]:
#             x += 1
# print(x)

#TLE改良版
a.sort()
for i in range(n-1):
    if a[i] == a[i+1]:
        for j in range(i+1, n):
            if a[i] == a[j]:
                x += 1
            else:
                break
    else:
        continue

#いらない処理
# y = 0
# for i in range(1, x+1):
#     y += i

print(x)

### FIXED CODE ###

import math
n = int(input())
a = list()
d = dict()
for i in range(n):
    b = list(input())
    b.sort()
    moji = "".join(b)
    if (moji in d):
        d[moji] += 1
    else:
        d[moji] = 1
x = 0
for i in d:
    if d[i] >=1:
        x += d[i]*(d[i]-1)/2
print(int(x))

#非最適化ソート
# for i in range(n):
#     a.append(input())
# for i, youso in enumerate(a):
#     b = list()
#     for j in youso:
#         b.append(j)
#     b.sort()
#     x = str()
#     for j in b:
#         x += j
#         a[i] = x

#TLE ver.
# for i, youso in enumerate(a):
#     for j in range(i, n-1):
#         if youso == a[j+1]:
#             x += 1
# print(x)

#TLE改良版
# a.sort()
# for i in range(n-1):
#     if a[i] == a[i+1]:
#         for j in range(i+1, n):
#             if a[i] == a[j]:
#                 x += 1
#             else:
#                 break
#     else:
#         continue



#いらない処理
# y = 0
# for i in range(1, x+1):
#     y += i
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))

ans = 0
min_v = N

for i in range(0, N):
    if P[i] > min_v: continue
    for j in range(0, i+1):
        if P[i] > P[j]:
            break

        if i == j:
            ans += 1
            min_v = P[i]

print (ans)




### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))

ans = 0
min_v = P[0]

for i in range(0, N):
    if P[i] <= min_v:
        ans += 1
        min_v = P[i]

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

import sys
from collections import Counter


def main():
    H, W, M = map(int, sys.stdin.readline().rstrip().split())
    Mh = [0] * H
    Mw = [0] * W
    B = []
    for i in range(M):
        h, w = map(int, sys.stdin.readline().rstrip().split())
        Mh[h - 1] += 1
        Mw[w - 1] += 1
        B.append((h - 1, w - 1))

    nh = max(Mh)
    nw = max(Mw)

    # 交差する場所に置かれた処理物があるか？
    lh = []
    lw = []
    while nh in Mh:
        ih = Mh.index(nh)
        lh.append(ih)
        Mh[ih] = 0
    while nw in Mw:
        iw = Mw.index(nw)
        lw.append(iw)
        Mw[iw] = 0

    for h in lh:
        for w in lw:
            if (h, w) not in B:
                print(nh + nw)
                return

    print(nh + nw - 1)


main()


### FIXED CODE ###

import sys
from collections import Counter


def main():
    H, W, M = map(int, sys.stdin.readline().rstrip().split())
    Mh = [0] * H
    Mw = [0] * W
    B = []
    for i in range(M):
        h, w = map(int, sys.stdin.readline().rstrip().split())
        Mh[h - 1] += 1
        Mw[w - 1] += 1
        B.append((h - 1, w - 1))

    nh = max(Mh)
    nw = max(Mw)

    # 交差する場所に置かれた処理物があるか？
    lh = Counter(Mh)[nh]
    lw = Counter(Mw)[nw]

    out = 0
    for (h, w) in B:
        if Mh[h] == nh and Mw[w] == nw:
            out += 1

    if out == lh * lw:
        print(nh + nw - 1)
    else:
        print(nh + nw)


main()
### BUGGY CODE ###

n = int(input())
L =sorted([int(i) for i in input().split()],reverse=True)

#print(L)

count=0
for i in range(0, n-2,1):
  x=0
  for j in range(i+1,n-1,1):
    for k in range(j+1,n,1):
      if (L[j] + L[k] > L[i]):
        count +=1
      else:
        if k == j+1:
          x=1
        break
    if x==1:
      break

print(count)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(N):
    for j in range(i+1,N):
        ans += bisect_left(L, L[i]+L[j])-j-1
print(ans)
### BUGGY CODE ###

import sys

N = int(input())
A = list(map(int,input().split()))
amari = 10**9 + 7

if N % 2 == 0:
    for i in range(1,N,2):
        if A.count(i) != 2:
            print("0")
            sys.exit()
else:
    if A.count(0) != 1:
        print("0")
        sys.exit()
    for i in range(2,N,2):
        if A.count(i) != 2:
            print("0")
            sys.exit()

print(2**(N//2) % amari)

### FIXED CODE ###

N = int(input())
A = sorted(list(map(int,input().split())))
amari = 10**9 + 7
ans = []
han = 0

if N % 2 == 0:
    han = 1
else:
    han = 0
    A.insert(0,0)


ans = list(int(i) for i in range(han,N,2))
ans += ans
ans.sort()

if ans == A:
    print(2**(N//2) % amari)
else:
    print("0")
### BUGGY CODE ###

def LI(): return [int(x) for x in input().split(" ")]
def LS(): return [str(x) for x in input().split(" ")]
def ItoS(L): return [str(x) for x in L]
def StoI(L): return [int(c) for c in L]


def solve():
    n, t = LI()
    T = LI()
    sentou = [0 for _ in range(T[-1] + t + 1)]

    i = 0
    while i < len(T):
        sentou[T[i]] += 1
        sentou[T[i] + t] -= 1
        i += 1

    j = 1
    while j < len(sentou):
        sentou[j] += sentou[j - 1]
        j += 1

    print(n * t - (sum(sentou) - (sentou.count(1) + len(sentou) - sentou.count(1) - sentou.count(0))))

solve()

### FIXED CODE ###

def LI(): return [int(x) for x in input().split(" ")]
def LS(): return [str(x) for x in input().split(" ")]
def ItoS(L): return [str(x) for x in L]
def StoI(L): return [int(c) for c in L]


def solve():
    n, t = LI()
    T = LI()

    ans = 0
    for i in range(len(T) - 1):
        ans += min(t, T[i + 1] - T[i])

    print(ans + t)


solve()
### BUGGY CODE ###

N = int(input())

for i in range(1 , 10 ** 6 + 1):
  for j in range(1 , 10 ** 6 + 1):
    if i * j == N:
      I = i - 1
      J = j - 1
      break
      
print(I * J)

### FIXED CODE ###

import math

N = int(input())
n = math.sqrt(N)
ans = 10 ** 12

for i in range(1 , math.ceil(n) + 1):
  if i * (N // i) == N:
    count = (i - 1) + ((N // i) - 1)
    ans = min(ans , count)
    
print(ans)
### BUGGY CODE ###

import math
b=[]
b.append(1)
b.append(2)
count=1
s=0
while s<30:
    try:
        x=int(input())
        if x>b[count]:
            for i in range(b[count]+1,x+1):
                count1=0
                
                for j in range(2,int(math.sqrt(i))+1):
                    if i%j==0:
                        count1=1
                        break
                if count1==0:
                    count+=1
                    b.append(i)
            print(count)
        else:
            for i in range(count+1):
                if b[i]>x:
                    print(i-1)
                    break
                elif b[i]==x:
                    print(i)
                    break
        s+=1
    except EOFError:
        break

### FIXED CODE ###

str1=[0 for i in range(10**6)]
str1[0]=1
str1[1]=1
for i in range(2,(10**6)):
    if str1[i]==0:
        for j in range(2,(10**6)):
            if i*j>=len(str1):
                break
            else:
                str1[i*j]=1
            
while 1 :
    try:
        x=int(input())
        count=0
        for i in range(1,x+1):
            if str1[i]==0:
                count+=1
        print(count)
        
    except EOFError:
        break
### BUGGY CODE ###

class UnionFind(object):

    def __init__(self, N):
        self._tree = [i for i in range(N)]
        self._rank = [0] * (N + 1)

    def find(self, x):
        if self._tree[x] == x:
            return x
        else:
            self._tree[x] = self.find(self._tree[x])
            return self._tree[x]

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

        # ランクを考慮しない場合はどちらが親になっても良い
        if self._rank[x] < self._rank[y]:
            self._tree[x] = y
        else:
            self._tree[y] = x

        if self._rank[x] == self._rank[y]:
            self._rank[x] += 1

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


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


def calc_inconvenience(unionfind, N):
    inconvenience = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            if not unionfind.has_same_parent(i, j):
                inconvenience += 1
    return int(inconvenience / 2)


result = list()
unionfind = UnionFind(N + 1)
for a, b in reversed(A_B):
    result.append(calc_inconvenience(unionfind, N))
    unionfind.unite(a, b)
for r in reversed(result):
    print(r)




### FIXED CODE ###

class UnionFind(object):

    def __init__(self, N):
        self._tree = [i for i in range(N)]
        self._rank = [0] * (N + 1)
        self.size = [1] * N
        self.inconvenience = N * (N - 1) // 2

    def find(self, x):
        if self._tree[x] == x:
            return x
        else:
            self._tree[x] = self.find(self._tree[x])
            return self._tree[x]

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

        if x == y:
            return

        self.inconvenience -= self.size[x] * self.size[y]
        if self._rank[x] < self._rank[y]:
            self._tree[x] = y
            self.size[y] += self.size[x]
        else:
            self._tree[y] = x
            self.size[x] += self.size[y]

        if self._rank[x] == self._rank[y]:
            self._rank[x] += 1


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

result = list()
uf = UnionFind(N)
for a, b in reversed(A_B):
    result.append(max(0, uf.inconvenience))
    uf.unite(a - 1, b - 1)
for r in reversed(result):
    print(r)
### BUGGY CODE ###

import collections
N = int(input())
all = []
count = []
for i in range(N):
  tmp = list(input())
  all.append(tmp.copy())
  count.append(collections.Counter(tmp))
nsame = 0
for i in range(N):
  for j in range(i+1, N):
    if count[i] == count[j]:
      nsame = nsame + 1
print(nsame)

### FIXED CODE ###

N = int(input())
alldict = {}
nsame = 0
for i in range(N):
  tmp = list(input())
  tmp.sort()
  if ''.join(tmp) in alldict:
    alldict[''.join(tmp)] = alldict[''.join(tmp)] + 1
  else:
    alldict[''.join(tmp)] = 1

from operator import mul
from functools import reduce
def cmb(n,r):
    if n == 1:
        return 0
    r = min(n-r,r)
    if r == 0:
        return 1
    ov = reduce(mul, range(n, n-r, -1))
    un = reduce(mul, range(1, r+1))
    return ov // un

print(sum([cmb(i, 2) for i in alldict.values()]))