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

import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def nibutan(n,list):
    left = 0
    right = len(list)
    while left+1 != right:
        middle = (left+right)//2
        if list[middle] <= n:
            left = middle
        else:
            right = middle
    return left+1

N,M,Q = IL()

l = [[] for i in range(N+1)]

for i in range(M):
    a,b = IL()
    l[a].append(b)

for i in l:
    i.sort()

Ql = [IL() for i in range(Q)]

for i in range(Q):
    cnt = 0
    start, end = Ql[i]
    for j in range(start,end+1):
        if len(l[j]) == 0:
            continue
        if l[j][0] > end:
            continue
        elif l[j][-1] <= end:
            cnt += len(l[j])
        else:
            cnt += nibutan(end,l[j])
    print(cnt)

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def imos():
  for j in range(N+1):
    cnt = 0
    for i in range(N+1):
      tmp = l[j][i]
      l[j][i] += cnt
      cnt += tmp

  for j in range(N+1):
    cnt = 0
    for i in range(N+1):
      tmp = l[i][j]
      l[i][j] += cnt
      cnt += tmp

N,M,Q = IL()
l = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
  a,b = IL()
  l[1][b] += 1
  if a+1 <= N:
    l[a+1][b] += -1

imos()

ans = [IL() for i in range(Q)]
for i in range(Q):
    print(l[ans[i][0]][ans[i][1]])
### BUGGY CODE ###

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

#N = int(input())
#S = input()

N = int(5e3)
S = 'a' *N

ans = 0
for circ in range(1, N):
  cnt = 0
  solver = [0]
  for i in range(N-circ):
    if S[i] == S[i+circ]:
      cnt += 1
    else:
      solver.append(cnt)
      cnt = 0
  else:
    solver.append(cnt)
  ans = max(ans, min(circ, max(solver)))

print(ans)




"""
ans = 0
for i in range(N-1):
  if i+1+ans >= N:
    break
  lst = [0]
  for j in range(i+1+ans,N):
    cnt = 0
    if S[i] == S[j]:
      cnt += 1
      for k in range(1,min(j-i, N-j)):
        if S[i+k] == S[j+k]:
          cnt += 1
        else:
          break
    lst.append(cnt)
    #print(i, j, cnt)
  ans = max(ans, max(lst))
  
print(ans)
"""

### FIXED CODE ###

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

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

#N = int(5e3)
#S = 'a' *N

ans = 0
for circ in range(1, N):
  cnt = 0
  solver = [0]
  for i in range(N-circ):
    if S[i] == S[i+circ]:
      cnt += 1
    else:
      solver.append(cnt)
      cnt = 0
  else:
    solver.append(cnt)
  ans = max(ans, min(circ, max(solver)))

print(ans)




"""
ans = 0
for i in range(N-1):
  if i+1+ans >= N:
    break
  lst = [0]
  for j in range(i+1+ans,N):
    cnt = 0
    if S[i] == S[j]:
      cnt += 1
      for k in range(1,min(j-i, N-j)):
        if S[i+k] == S[j+k]:
          cnt += 1
        else:
          break
    lst.append(cnt)
    #print(i, j, cnt)
  ans = max(ans, max(lst))
  
print(ans)
"""
### BUGGY CODE ###

import math
result=[]; a, b, n = list(map(int,input().split()))
for x in range(n+1):
     result.append((math.floor(a*x / b)) - (a* math.floor(x/b)))
else:
    print(max(result))

### FIXED CODE ###

a, b, n = map(int,input().split())
x = min(n,b-1)
print(int(a*(x%b) / b))
### BUGGY CODE ###

s = input()

def get_sum(J, I, L, K):
    total1 = int(I * 3 ** J + J * 3 ** (J - 1))
    total2 = int(K * 3 ** L + L * 3 ** (L - 1))
    return total1 * total2

n_q_right = [0]
n_a_right = [0]
n_c_right = [0]
n_q = 0
n_c = 0
for i in range(len(s) - 1):
    if s[i] == '?':
        n_q_right.append(n_q_right[-1] + 1)
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])
        n_q += 1
    elif s[i] == 'A':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1] + 1)
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'C':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1] + 1)
        n_c += 1
    elif s[i] == 'B':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])

if s[-1] == '?':
    n_q += 1
elif s[-1] == 'C':
    n_c += 1

n_q_left = []
n_c_left = []
total = 0
for i in range(len(s)):
    if s[i] == '?':
        n_q_left.append(n_q - n_q_right[i] - 1)
        n_c_left.append(n_c - n_c_right[i])
        total += get_sum(n_q_right[i], n_a_right[i], n_q_left[i], n_c_left[i]) %  (10 ** 9 + 7)
    elif s[i] == 'A':
        n_q_left.append(n_q - n_q_right[i])
        n_c_left.append(n_c - n_c_right[i])
    elif s[i] == 'C':
        n_q_left.append(n_q - n_q_right[i])
        n_c_left.append(n_c - n_c_right[i] - 1)
    elif s[i] == 'B':
        n_q_left.append(n_q - n_q_right[i])
        n_c_left.append(n_c - n_c_right[i])
        total += get_sum(n_q_right[i], n_a_right[i], n_q_left[i], n_c_left[i]) %  (10 ** 9 + 7)



print(total % (10 ** 9 + 7))


### FIXED CODE ###

s = input()
a, d = [0], [0]
for char in s[:-1]:
    if char == 'A':
        a.append(a[-1] + 1)
    else:
        a.append(a[-1])
    if char == '?':
        d.append(d[-1] + 1)
    else:
        d.append(d[-1])

c, e = [0], [0]
for char in s[::-1][:-1]:
    if char == 'C':
        c.append(c[-1] + 1)
    else:
        c.append(c[-1])
    if char == '?':
        e.append(e[-1] + 1)
    else:
        e.append(e[-1])
c = c[::-1]
e = e[::-1]

ret = 0
mod = 10 ** 9 + 7
for char, aa, dd, cc, ee in zip(s, a, d, c, e):
    if char in 'B?':
        tmp1 = aa * pow(3, dd, mod)
        if dd != 0:
            tmp1 += dd * pow(3, dd - 1, mod)

        tmp2 = cc * pow(3, ee, mod)
        if ee != 0:
            tmp2 += ee * pow(3, ee - 1, mod)

        ret += tmp1 * tmp2
        ret %= mod

print(ret)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n = int(input())

stations = []

for i in range(n - 1):
    c, s, f = map(int, input().split())
    stations += [dict(c = c, s = s, f = f)]

for i in range(n - 1):
    time = stations[i]['s'] + stations[i]['c']
    i += 1
    while i < n - 1:
        n_time = stations[i]['s']
        while time > n_time:
            n_time += stations[i]['f']
        time = n_time + stations[i]['c']
        i += 1
    print(str(time))
print(str(0))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math

n = int(input())
sta = []

for i in range(n - 1):
    c, s, f = map(int, input().split())
    sta += [dict(c = c, s = s, f = f)]

for i in range(n):
    time = 0
    while i < n - 1:
        x = math.ceil((time - sta[i]['s']) / sta[i]['f']) if time > sta[i]['s'] else 0
        time = sta[i]['s'] + sta[i]['f'] * x + sta[i]['c']
        i += 1
    print(str(time))
### BUGGY CODE ###

def make_ac_list(list):
    ac_list = []
    co_list = []
    for i,k in enumerate(list):
        if k[1] == 'AC' and k[0] not in co_list:
            ac_list.append([int(k[0]),i])
            co_list.append(k[0])
    return ac_list

def count_penalty(array,list):
    penalty = 0
    for i,k in enumerate(list):
        for j in range(k[1]):
            if array[j] == [str(k[0]),'WA']:
                penalty += 1

    return penalty 


def main():
    n,m = map(int, input().split())
    s = [list(input().split()) for i in range(m)]

    ac_list = make_ac_list(s)
    correct = len(ac_list)
    penalty = count_penalty(s,ac_list)

    print('{} {}'.format(correct,penalty))


if __name__ == '__main__':
    main()

### FIXED CODE ###

n, m = map(int, input().split())
ac = 0
wa = 0
 
ac_tf = [0] * n
wa_num = [0] * n
 
for i in range(m):
    p, s = input().split()
    p = int(p) - 1
    if s == "AC":
        if ac_tf[p] == 0:
            ac += 1
            wa += wa_num[p]
            ac_tf[p] = 1
    else:
        wa_num[p] += 1
            
print(ac, wa)
### BUGGY CODE ###

k = int(input())
ans = 0

def lunlun(ans):
    a = True
    c = len(str(ans))
    for i in range(c-1):
        r1 = ans % 10
        ans = int(ans/10)
        r2 = ans % 10
        if abs(r1-r2) > 1:
            a = False
    return a

while k > 0:
    ans += 1
    if lunlun(ans):
        k -= 1

print(ans)

### FIXED CODE ###

k = int(input())
ans = 0
import queue

q = queue.Queue()
for i in range(1,10):
    q.put(i)

for i in range(k):
    ans = q.get()
    if ans%10 != 0:
        x = 10*ans + ans%10 - 1
        q.put(x)
    y = 10*ans + ans%10
    q.put(y)
    if ans%10 != 9:
        z = 10*ans + ans%10 + 1
        q.put(z)

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

N = int(input())
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  A, B = map(int, input().split())
  vec[A-1].append(B-1)
  vec[B-1].append(A-1)

sub_size = [[] for _ in range(N)]

def dfs(cur, pre) :
  s = 0
  for nex in vec[cur] :
    if nex == pre :
      continue
    t = dfs(nex, cur)
    s += t
    sub_size[cur].append(t)
  return s + 1

dfs(0, -1)

ret = 0
for i in range(N) :
  if sum(sub_size[i]) != N - 1 :
    sub_size[i].append(N - 1 - sum(sub_size[i]))
  
  if len(sub_size[i]) <= 1 :
    continue

fac = [1]
inv = [1]
for _ in range(N) :
  fac.append(fac[-1] * 2 % mod)
  inv.append(pow(fac[-1], mod - 2, mod))

for i in range(N) :
  a, b = 1, 1
  for ss in sub_size[i] :
    a *= inv[ss]
    b += fac[ss] - 1
    a %= mod
    b %= mod
  ret += (1 - a * b) % mod
  ret %= mod

ret = ret * inv[1] % mod

print(ret)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

N = int(input())
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  A, B = map(int, input().split())
  vec[A-1].append(B-1)
  vec[B-1].append(A-1)

own_size = [0] * N
sub_size = [[] for _ in range(N)]

# pythonのdfs重すぎて自分でstack書かないと通らない。
# く〜〜つらいとこね、これ！！！！
stack = [(0, -1)]
for i in range(N) :
  cur, pre = stack[i]
  for nex in vec[cur] :
    if nex != pre :
      stack.append((nex, cur))

while stack :
  cur, pre = stack.pop()
  if pre != -1 :
    sub_size[pre].append(own_size[cur] + 1)
    own_size[pre] += own_size[cur] + 1
  if own_size[cur] != N - 1 :
    sub_size[cur].append(N - 1 - own_size[cur])

fac = [1]
inv = [1]
div = pow(2, mod - 2, mod)
for _ in range(N) :
  fac.append(fac[-1] * 2 % mod)
  inv.append(inv[-1] * div % mod)

ret = 0
for i in range(N) :
  if len(sub_size[i]) < 2 :
    continue

  a, b = 1, 1
  for ss in sub_size[i] :
    a *= inv[ss]
    b += fac[ss] - 1
    a %= mod
    b %= mod
  ret += (1 - a * b) % mod
  ret %= mod

ret = ret * div % mod

print(ret)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
count = 0
rgb = sorted([R, G, B], reverse=True)
for i in range(N+1):
    for j in range(N+1):
        tmp = N - (rgb[0] * i + rgb[1] * j)
        if 0 > tmp:
            break
        if tmp % rgb[2] == 0:
            count += 1

print(count)


### FIXED CODE ###

R, G, B, N = map(int, input().split())
count = 0
rgb = sorted([R, G, B], reverse=True)
if False:
    count = 0
else:
    for i in range(N+1):
        for j in range(N+1):
            tmp = N - (rgb[0] * i + rgb[1] * j)
            if 0 > tmp:
                break
            if tmp % rgb[2] == 0:
                count += 1
print(count)
### BUGGY CODE ###

r,g,b,n =  map(int,input().split())
cnt=0
for i in range(n//r+1):
    for j in range(n//g+1):
        #print(i,j)
        #print(n-i*r-j*g)
        if int(n-(i*r)-(j*g)) % b ==0 and int(n-(i*r)-(j*g)) >=0 :
            #print("a")
            #print(i,j)
            cnt+=1
print(cnt)


### FIXED CODE ###

r,g,b,n =  map(int,input().split())
cnt=0
for i in range(n//r+1):
    for j in range(n//g+1):
        #print(i,j)
        #print(n-i*r-j*g)
        if int(n-(i*r)-(j*g)) % b ==0 and int(n-(i*r)-(j*g)) >=0 :
            #print("a")
            #print(i,j)
            cnt+=1
print(cnt)
### BUGGY CODE ###

n,m=[int(x) for x in input().rstrip().split()]
a=[int(x) for x in input().rstrip().split()]

for i in range(m):
  b,c=[int(x) for x in input().rstrip().split()]
  a.extend([c]*b)
a.sort(reverse=True)
print(sum(a[:n]))


### FIXED CODE ###

n,m=[int(x) for x in input().rstrip().split()]
a=[int(x) for x in input().rstrip().split()]
a.sort(reverse=True)
d=[]
bc=[]
for i in range(m):
  b,c=[int(x) for x in input().rstrip().split()]
  bc.append([b,c])

cnt=0
bc.sort(key=lambda x:x[1],reverse=True)
for b,c in bc:

  d.extend([c]*b)
  cnt+=b
  if n<cnt:
    break
  
d.sort(reverse=True)
a+=d
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

a = 1
b = 1
c = 1
d = 0

for i in range(K):
    
    for j in range(K):
        
        for k in range(K):
            d = gcd(gcd(a, b), c) + d
            c = c + 1
            
        
        c = 1
        b = b + 1
    
    b = 1
    a = a + 1
    
print(d)

### FIXED CODE ###

from math import gcd

K = int(input()) + 1
d = 0

for i in range(1, K):
    for j in range(1, K):
        for k in range(1, K):
            d = gcd(gcd(i, j), k) + d
print(d)
### BUGGY CODE ###

a, b, x = map(int, input().split())

s = 0

for cnt in range(a, b+1):
    if cnt % x == 0 :
        s += 1
    else:
        continue
        
print(s)

### FIXED CODE ###

a,b,x=map(int,input().split())
print(b//x-(a-1)//x)
### BUGGY CODE ###

from collections import Counter


def main():

    N = int(input())
    S = input()
    count = Counter(S)

    # print(count)
    ans = 0
    R = count["R"]
    G = count["G"]
    B = count["B"]
    ans = R * G * B

    # for i in range(N - 2):
    #     if S[i] == "R":
    #         for j in range(i + 1, N - 1):
    #             if S[j] == "G":
    #                 b_count = Counter(S[j:])["B"]
    #                 ans += b_count

    # print(R, G, B, ans)

    for i in range(N):
        for j in range(N):
            if i + j * 2 < N and S[i] == "R" and S[i + j] == "G" and S[i + j * 2] == "B":
                ans -= 1
            if i + j * 2 < N and S[i] == "R" and S[i + j] == "B" and S[i + j * 2] == "G":
                ans -= 1
            if i + j * 2 < N and S[i] == "G" and S[i + j] == "R" and S[i + j * 2] == "B":
                ans -= 1
            if i + j * 2 < N and S[i] == "G" and S[i + j] == "B" and S[i + j * 2] == "R":
                ans -= 1
            if i + j * 2 < N and S[i] == "B" and S[i + j] == "G" and S[i + j * 2] == "R":
                ans -= 1
            if i + j * 2 < N and S[i] == "B" and S[i + j] == "R" and S[i + j * 2] == "G":
                ans -= 1
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter

N = int(input())
S = input()
count = Counter(S)

# print(count)
ans = 0
R = count["R"]
G = count["G"]
B = count["B"]
ans = R * G * B

# for i in range(N - 2):
#     if S[i] == "R":
#         for j in range(i + 1, N - 1):
#             if S[j] == "G":
#                 b_count = Counter(S[j:])["B"]
#                 ans += b_count

# print(R, G, B, ans)

for i in range(N):
    for j in range(N):
        if i + j * 2 < N and S[i] == "R" and S[i + j] == "G" and S[i + j * 2] == "B":
            ans -= 1
        if i + j * 2 < N and S[i] == "R" and S[i + j] == "B" and S[i + j * 2] == "G":
            ans -= 1
        if i + j * 2 < N and S[i] == "G" and S[i + j] == "R" and S[i + j * 2] == "B":
            ans -= 1
        if i + j * 2 < N and S[i] == "G" and S[i + j] == "B" and S[i + j * 2] == "R":
            ans -= 1
        if i + j * 2 < N and S[i] == "B" and S[i + j] == "G" and S[i + j * 2] == "R":
            ans -= 1
        if i + j * 2 < N and S[i] == "B" and S[i + j] == "R" and S[i + j * 2] == "G":
            ans -= 1
print(ans)
### BUGGY CODE ###

s = input()
t = input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ""
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += s[i-1]
        i -= 1
        j -= 1
print(ans[::-1])

### FIXED CODE ###

s = input()
t = input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ""
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += s[i-1]
        i -= 1
        j -= 1
print(ans[::-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
sumFrontHalf=0
halfIndex=0
for i in range(n):
  sumFrontHalf+=a[i]
  if sumFrontHalf>=sum(a)/2:
    halfIndex=i
    break
sumBackHalf=sum(a)-sumFrontHalf+a[halfIndex]
if sumFrontHalf<sumBackHalf:
  print(sumFrontHalf-sumBackHalf+a[halfIndex])
else:
  print(sumBackHalf-sumFrontHalf+a[halfIndex])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
sumFrontHalf=0
halfIndex=0
sumA=sum(a)
for i in range(n):
  sumFrontHalf+=a[i]
  if sumFrontHalf>=sumA/2:
    halfIndex=i
    break
sumBackHalf=sumA-sumFrontHalf+a[halfIndex]
if sumFrontHalf<sumBackHalf:
  print(sumFrontHalf-sumBackHalf+a[halfIndex])
else:
  print(sumBackHalf-sumFrontHalf+a[halfIndex])
### BUGGY CODE ###

class UnionFind:
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rnk = [0]*(n+1)
		self.Maxroot = -1

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

	def Unite(self, x, y):
		x = self.Find_Root(x)
		y = self.Find_Root(y)
		if x == y:
			return 
		elif self.rnk[x] > self.rnk[y]:
			self.root[x] += self.root[y]
			if self.root[x] < self.Maxroot:
				self.Maxroot = self.root[x]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			if self.root[y] < self.Maxroot:
				self.Maxroot = self.root[y]
			self.root[x] = y
			if self.rnk[x] == self.rnk[y]:
				self.rnk[y] += 1

	def isSameGroup(self, x, y):
		return self.Find_Root(x) == self.Find_Root(y)

	def Count(self, x):
		return self.root[self.Find_Root(x)] * (-1)

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

solve = UnionFind(N)
ans = [0]
for i in reversed(range(M)):
	tmp = 0
	solve.Unite(a[i], b[i])
	for i in range(1,N+1):
		if solve.root[i] < -1:
			t = solve.root[i]*(-1)
			tmp += t*(t-1)//2
	ans.append(tmp)
			
tot = N*(N-1)//2

for i in range(1,len(ans)):
	print(tot-ans[-(i+1)])

### FIXED CODE ###

class UnionFind:
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rnk = [0]*(n+1)
		self.Maxroot = -1

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

	def Unite(self, x, y):
		x = self.Find_Root(x)
		y = self.Find_Root(y)
		if x == y:
			return 
		elif self.rnk[x] > self.rnk[y]:
			self.root[x] += self.root[y]
			if self.root[x] < self.Maxroot:
				self.Maxroot = self.root[x]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			if self.root[y] < self.Maxroot:
				self.Maxroot = self.root[y]
			self.root[x] = y
			if self.rnk[x] == self.rnk[y]:
				self.rnk[y] += 1

	def isSameGroup(self, x, y):
		return self.Find_Root(x) == self.Find_Root(y)

	def Count(self, x):
		return self.root[self.Find_Root(x)] * (-1)

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

solve = UnionFind(N)
ans = [0]
for i in reversed(range(M)):
	ca,cb = a[i],b[i]
	if solve.isSameGroup(ca,cb):
		ans.append(ans[-1])
		continue
	num_group_a = solve.Count(ca)
	num_group_b = solve.Count(cb)
	tmp = num_group_a * num_group_b
	solve.Unite(ca, cb)
	ans.append(ans[-1]+tmp)
			
tot = N*(N-1)//2

for i in range(2,M+2):
	print(tot-ans[-i])
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
cnt = 0
for i in set(a):
    cnt += a.count(i) % 2
print(cnt)

### FIXED CODE ###

import collections
n = int(input())
a = [int(input()) for _ in range(n)]
A = collections.Counter(a)
ans = 0
for i in A.values():
    if i % 2 != 0:
        ans += 1
print(ans)
### BUGGY CODE ###

s = list(input())
n=int(input())
l = [input().split(" ") for _ in range(n)]

x = 0
for i in range(n):
    if l[i][0]=='1':
        if x == 0:
            x = 1
        else:
            x = 0
    elif l[i][0]=='2':
        if x == 0:
            if l[i][1]=='1':
                s = [l[i][2]] + s
            else:
                s.append(l[i][2])
        else:
            if l[i][1]=='1':
                s.append(l[i][2])
            else:
                s = [l[i][2]] + s
if x == 0:
    print(''.join(s))
else:
    print(''.join(s[::-1]))

### FIXED CODE ###

from collections import deque

s = deque(input())
n = int(input())
l = [input().split(" ") for _ in range(n)]

x = 0
for i in range(n):
    if l[i][0]=='1':
        if x == 0:
            x = 1
        else:
            x = 0
    elif l[i][0]=='2':
        if x == 0:
            if l[i][1]=='1':
                s.appendleft(l[i][2])
            else:
                s.append(l[i][2])
        else:
            if l[i][1]=='1':
                s.append(l[i][2])
            else:
                s.appendleft(l[i][2])

if x == 0:
    print(''.join(s))
else:
    print(''.join(reversed(s)))
### BUGGY CODE ###

N, K = map(int, input().split())  # N個の足場, K段飛ぶことができる

H = list(map(int, input().split()))

dp = [1e+9]*N
dp[0] = 0
dp[1] = abs(H[1]-H[0])

for i in range(2, N):
    # Kステップ前まで考慮する必要
    for j in range(1, min(i, K)+1):
        dp[i] = min(dp[i], dp[i-j]+abs(H[i]-H[i-j]))

print(dp[-1])


### FIXED CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]


def frog(n, k, h):
    d = [float('inf')] * n
    d[0] = 0

    for i in range(1, n):
        d[i] = min(
            d[j] + abs(h[i] - h[j]) for j in range(max(i - k, 0), i)
        )
    return d[n - 1]


print(frog(n, k, h))
### BUGGY CODE ###

def binary_search(list, item):
    low = 0
    high = len(list) - 1
    
    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    return -1

if __name__ == '__main__':
    N = int(input())
    l = []
    for i in range(N):
        word = input()
        index = binary_search(l,word)
        if  index == -1:
            l.append(word)
        l = sorted(l)
    print(len(l))


### FIXED CODE ###

N = int(input())
l = []
for i in range(N):
    l.append(input())
l = sorted(l)
new_list = []
new_list.append(l[0])
for i in range(1,len(l)):
    if l[i-1] != l[i]:
        new_list.append(l[i])
print(len(new_list))
### BUGGY CODE ###

K = int(input())
ans = 1
sev = 7

while sev%K:
  ans+=1
  sev=(10*sev+7)%K
else:
  print(ans)
  exit()

print(-1)

### FIXED CODE ###

K = int(input())
a = 7

for n in range(1,1+K):
  if a%K==0:
    print(n)
    exit()
  a = (a*10+7)%K

print(-1)
### BUGGY CODE ###

import sys
n,y=map(int,input().split())
if n*10000<y:
    print("-1 -1 -1")
    sys.exit()
if y//1000<n:
    print("-1 -1 -1")
    sys.exit()
m=y//10000
g=y//5000
for i in range(m+1):
    for j in range(g+1):
        s=(y-10000*i-5000*j)//1000
        if i+j+s==n and s>=0:
            print(i,j,s)
            sys.exit()
print("-1 -1 -1")

### FIXED CODE ###

import sys
n,y=map(int,input().split())
if n*10000<y:
    print("-1 -1 -1")
    sys.exit()
if y//1000<n:
    print("-1 -1 -1")
    sys.exit()
m=y//10000
for i in range(m+1):
    g=(y-i*10000)//5000
    for j in range(g+1):
        s=(y-10000*i-5000*j)//1000
        if i+j+s==n and s>=0:
            print(i,j,s)
            sys.exit()
print("-1 -1 -1")