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

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

rList = []
gList = []
bList = []

for indx in range(N):
    if S[indx] == 'R':
        rList.append(indx)
    elif S[indx] == 'G':
        gList.append(indx)
    elif S[indx] == 'B':
        bList.append(indx)

NoSum = 0
fList = rList
sList = gList
remain = 'B'

for fItem in fList:
    for sItem in sList:
        if (max(fItem, sItem) + (max(fItem, sItem) - min(fItem, sItem)) <= N-1):
            if (S[max(fItem, sItem) + (max(fItem, sItem) - min(fItem, sItem))] == remain):
                NoSum += 1
        
        if ((max(fItem, sItem) - min(fItem, sItem)) % 2 == 0):
            if (S[int((max(fItem, sItem) + min(fItem, sItem))/2)] == remain):
                NoSum += 1
        
        if (min(fItem, sItem) - (max(fItem, sItem) - min(fItem, sItem)) >= 0):
            if  (S[min(fItem, sItem) - (max(fItem, sItem) - min(fItem, sItem))] == remain):
                NoSum += 1

print(len(rList) * len(gList) * len(bList) - NoSum)

### FIXED CODE ###

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

rList = []
gList = []
bList = []

for indx in range(N):
    if S[indx] == 'R':
        rList.append(indx)
    elif S[indx] == 'G':
        gList.append(indx)
    elif S[indx] == 'B':
        bList.append(indx)

NoSum = 0
fList = rList
sList = gList
remain = 'B'

for fItem in fList:
    for sItem in sList:
        prsMax = max(fItem, sItem)
        prsMin = min(fItem, sItem)
        if ((2 * prsMax - prsMin) <= N-1):
            if (S[(2 * prsMax - prsMin)] == remain):
                NoSum += 1
        
        if ((prsMax - prsMin) % 2 == 0):
            if (S[int((prsMax + prsMin)/2)] == remain):
                NoSum += 1
        
        if ((2 * prsMin - prsMax) >= 0):
            if  (S[(2 * prsMin - prsMax)] == remain):
                NoSum += 1

print(len(rList) * len(gList) * len(bList) - NoSum)
### BUGGY CODE ###

a, b = map(int, input().split())
cnt = 1
i = 2
c, d = a, b

while d > 0:
    c, d = d, c % d

while c > 1:
    if c % i == 0:
        cnt += 1
        
        while c % i == 0:
            c //= i

    i += 1

print(cnt)

### FIXED CODE ###

import math

a, b = map(int, input().split())
cnt = 1
i = 2
c, d = a, b

while d > 0:
    c, d = d, c % d

k = int(math.sqrt(c))

while c > 1:
    if c % i == 0:
        cnt += 1
        
        while c % i == 0:
            c //= i

    i += 1

    if k < i:
        cnt += 1
        break

print(cnt)
### BUGGY CODE ###

from collections import deque
N=int(input())
numbers=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    numbers[a].append((b,c))
    numbers[b].append((a,c))
Q,K=map(int,input().split())
K-=1
keika=[]
for _ in range(Q):
    x,y=map(int,input().split())
    keika.append([x-1,y-1])
inf=pow(10,10)
visited=[inf for _ in range(N)]
visited[K]=0
stack=deque([K])
while len(stack)>0:
    n=stack.pop()
    for s,t in numbers[n]:
        if visited[s]==inf:
            stack.appendleft(s)
            visited[s]=min(visited[s],visited[n]+t)
for z in keika:
    print(visited[z[0]]+visited[z[1]])


### FIXED CODE ###

from collections import deque
import heapq
N=int(input())
numbers=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    numbers[a].append((b,c))
    numbers[b].append((a,c))
Q,K=map(int,input().split())
K-=1
keika=[]
for _ in range(Q):
    x,y=map(int,input().split())
    keika.append([x-1,y-1])
inf=pow(10,10)
visited=[inf for _ in range(N)]
visited[K]=0
stack=[K]
heapq.heapify(stack)
while len(stack)>0:
    n=heapq.heappop(stack)
    for s,t in numbers[n]:
        if visited[s]==inf:
            heapq.heappush(stack,s)
            visited[s]=visited[n]+t
for z in keika:
    print(visited[z[0]]+visited[z[1]])
### BUGGY CODE ###

import itertools
n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

c = []
for i in range(n):
    c.append((a[i], b[i]))


l = [i+1 for i in range(n)]
ans = 10**9

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


for v in itertools.permutations(l, n):
    tmp = 0
    cnt = 0
    for i in range(n):
        if tmp <= c[v[i]-1][(i-v[i]+1) % 2]:
            tmp = c[v[i]-1][(i-v[i]+1) % 2]
            cnt += 1
        else:
            break

    if cnt == n:
        bit = Bit(n)
        kaisu = 0
        for i in range(0, n):
            kaisu += i - bit.sum(v[i])
            bit.add(v[i], 1)
        ans = min(ans, kaisu)

print(ans if ans != 10**9 else -1)


### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

dp = [[10**9 for _ in range(51)] for __ in range(1 << n)]
dp[0][0] = 0


for i in range(1 << n):
    target = bin(i).count("1")-1
    cnt = bin(i).count("1")
    for j in range(n):
        if i >> j & 1:
            cnt -= 1
            if abs(j - target) % 2 == 0:
                nxt = a[j]
            else:
                nxt = b[j]
            for k in range(nxt+1):
                if dp[i ^ (1 << j)][k] != 10**9:
                    dp[i][nxt] = min(dp[i][nxt], dp[i ^ (1 << j)][k] + abs(j+cnt-target))

ans = min(dp[2**n-1])

print(ans if ans < 10**9 else -1)
### BUGGY CODE ###

from fractions import gcd
N = int(input())
As = list(map(int, input().split()))

lcm = 1
mod = 10**9+7

def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

from collections import defaultdict
def factorization(n):
    factors = defaultdict(int)
    if n == 2 or n == 3:
        factors[n] = 1
        return factors
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
            # print(factors,n)
    if n != 1:
        factors[n] += 1
    return factors

d = defaultdict(int)
factors_list = []
cnt_1 = 0
for a in As:
    if a == 1:
        cnt_1 += 1
        continue
    factors = factorization(a)
    factors_list.append(factors)
    for f in factors.keys():
        d[f] = max(d[f],factors[f])

for f in d.keys():
    lcm *= f ** d[f]

ans = sum([lcm//a for a in As])
print(ans%mod)

### FIXED CODE ###

from fractions import gcd
N = int(input())
As = list(map(int, input().split()))

lcm = 1
mod = 10**9+7

def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

from collections import defaultdict
def factorization(n):
    factors = defaultdict(int)
    if n == 2 or n == 3:
        factors[n] = 1
        return factors
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
            # print(factors,n)
    if n != 1:
        factors[n] += 1
    return factors

d = defaultdict(int)
factors_list = []
cnt_1 = 0
for a in As:
    if a == 1:
        cnt_1 += 1
        continue
    factors = factorization(a)
    factors_list.append(factors)
    for f in factors.keys():
        d[f] = max(d[f],factors[f])

for f in d.keys():
    lcm *= f ** d[f]
    lcm %= mod

As_inv = [pow(a,mod-2,mod) for a in As]
a = sum(As_inv)%mod



print((lcm*a)%mod)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline

N = int(input())

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

for i in range(N):
    print(l.count(i+1))

### FIXED CODE ###

from sys import stdin
input = stdin.readline

import collections

N = int(input())

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

c = collections.Counter(l)

[print(c[i+1]) for i in range(N)]
### BUGGY CODE ###

n,k,q = map(int, input().split())
a = [int(input()) for _ in range(q)]
p = [0]*n

if k>q:
    for i in range(n):
        print('Yes')
    exit()
else:
    for i in range(n):
        p[i]=a.count(i+1)
        if k+p[i]-q>0:
            print('Yes')
        else:
            print('No')

### FIXED CODE ###

n,k,q = map(int, input().split())
a = [int(input()) for _ in range(q)]

p = [k-q]*(n)
for i in a:
    p[i-1] +=1

for i in range(n):
    if p[i]>0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = float('inf')
for i in range(1, N):
    ans = min(ans, abs(sum(A[:i]) - sum(A[i:])))
print(ans)


### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
sum_A = np.sum(A)
cumsum_A = np.cumsum(A)

ans = float('inf')
for i in range(N - 1):
    ans = min(ans, abs(sum_A - 2 * cumsum_A[i]))
print(ans)
### BUGGY CODE ###

from functools import cmp_to_key
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
d.sort(key = cmp_to_key(lambda x, y: y[1] / y[0] - x[1] / x[0]))
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        for k in list(t.keys()):
          if k <= nw and t[k] <= nv:
            del t[k]
        t[nw] = nv
    else:
      Flag = False
      for k in t:
        if nw <= k and nv <= t[k]:
          Flag = True
          break
      if Flag:
        continue
      for k in list(t.keys()):
        if k <= nw and t[k] <= nv:
          del t[k]
      t[nw] = nv
        
print(max(t.values()))


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num, p = 0, i ,[0]
        for _ in range(h):
            p.append(p[-1]+num%2)
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]
        for j in range(w):
            num = i
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p[m]] += s[m][j]
            if max(nex) > k:
                x = float('inf')
                break            
            
            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))

### FIXED CODE ###

h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]
        
        num = i
        p = 0
        nex = [0 for _ in range(checker+1)]
        for m in range(h):
            nex[p] += s[m][0]
            p += num%2
            num = num >> 1
        if max(nex) > k:
            x = float('inf')
            continue

        if all(nex[m]+c[m] <= k for m in range(checker+1)):
            c = [c[I]+nex[I] for I in range(checker+1)]
        else:
            x += 1

        for j in range(1, w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1
            if max(nex) > k:
                x = float('inf')
                break            
            
            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))
### BUGGY CODE ###

import sys

N = int(sys.stdin.readline().strip())
l_list = list(sorted(list(map(int, sys.stdin.readline().strip().split(" ")))))
count = 0

for i in reversed(range(2, N)):
    t_max = l_list[i]
    point = None
    for j in range(0, i-1):
        if l_list[j]+l_list[i-1] > t_max:
            point = j
            break
    if point is None:
        continue
    count += (i-1-point)

    for j in reversed(range(point, i-1)):
        point_sec = point
        t_sec = l_list[j]
        flag = False
        for k in range(point_sec, j):
            if l_list[k]+l_list[j] > t_max:
                point_sec = k
                flag = True
                break
        if not flag:
            continue
        count += (j-point_sec)

print(count)

### FIXED CODE ###

import sys

def bi_search(array, target):
    l, r = -1, len(array)-1
    while r-l > 1:
        mid = int((r+l)/2)
        if array[mid] > target:
            r = mid
        else:
            l = mid
    return r

N = int(sys.stdin.readline().strip())
l_list = list(sorted(list(map(int, sys.stdin.readline().strip().split(" ")))))
count = 0
#print(l_list)

for i in reversed(range(N)):
    a = l_list[i]
    for j in reversed(range(i)):
        b = l_list[j]
        index = bi_search(l_list[:j], a-b)
        """
        print("====")
        print(b-a)
        print(i, j, index)
        """
        if index > -1 and index < j and l_list[index] + b > a:
            count += (j-index)

print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
s = list(input())

from collections import defaultdict
ans = defaultdict(int)
def dfs(now, pos):
    if len(now) == 3:
        ans[now] = 1
        return
    if pos == n:
        return
    dfs(now+s[pos], pos+1)
    dfs(now, pos+1)

dfs("", 0)

anss = 0
for i in ans.values():
    anss += i

print(anss)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
s = list(input())

ans = 0
num = [str(i) for i in range(10)]
for i in num:
    for l in range(n):
        if s[l] == i:
            for j in num:
                for m in range(l+1,n):
                    if s[m] == j:
                        for k in num:
                            for p in range(m+1, n):
                                if s[p] == k:
                                    ans += 1
                                    break
                            continue
                        break
            break

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

import numpy as np
import math

s = input()[::-1]
length = len(s)
a = np.zeros(length, dtype=int)
d = np.zeros(length, dtype=int)

for i in range(length):
    a[i] = int(s[i]) * pow(10, i) % 2019
d[0] = a[0]

for i in range(length-1):
    d[i+1] = (d[i] + a[i+1]) % 2019
    
x = np.unique(d, return_counts=True)[1]
x = x[np.where(x > 1)]

print(int(sum([math.factorial(x[i]) for i in range(x.shape[0])]) / 2) + d.shape[0] - np.count_nonzero(d))

### FIXED CODE ###

import numpy as np

s = input()[::-1]
length = len(s)
a = np.zeros(length, dtype=int)
d = np.zeros(length, dtype=int)
ans = np.zeros(2019, dtype=int)
x = 10

a[0] = int(s[0])
d[0] = a[0]
ans[d[0]] += 1

for i in range(1, length):
    a[i] = int(s[i]) * x % 2019
    d[i] = (d[i-1] + a[i]) % 2019
    ans[d[i]] += 1
    x = x * 10 % 2019

ans_c = ans[np.nonzero(ans)]

print(int(sum([ans_c[i] * (ans_c[i]-1) for i in range(ans_c.shape[0])]) / 2) + ans[0])
### BUGGY CODE ###

n = input()
n = n.split()
K,S = map(int, n)
count = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z == S:
                count += 1
print(count)

### FIXED CODE ###

arr = input().split()
k = int(arr[0])
s = int(arr[1])

count = 0
for x in range(k+1):
    for y in range(k+1):
        if s - x - y >= 0:
           z = s - x - y
           if z <= k:
               count += 1
print(count)
### BUGGY CODE ###

n , k , q = map(int, input().split())
a = [int(input()) for i in range(q)]
points = [k for i in range(n)]
for correct in range(n):
    for others in range(n):
        if correct == others:
            continue
        else:
            points[others - 1] -= a.count(correct)
for i in range(n):
    if points[i] >= 1:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

n , k , q = map(int, input().split())
points = [k - q] * n
for i in range(q):
    c = int(input())
    points[c-1] += 1
for i in range(n):
    if points[i] >= 1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n,k= map(int,input().split())
h = [int(i) for i in input().split()]
inf = 10**7
dp = [inf]*100005
dp[0] = 0
for i in range(1,n):
    dp[i] = min(dp[i-j] + abs(h[i-j] - h[i]) for j in range(1,min(k,i)+1))
print(dp[n-1])

### FIXED CODE ###

def main():
    n,k= map(int,input().split())
    h = [int(i) for i in input().split()]
    inf = 10**7
    dp = [inf]*100005
    dp[0] = 0
    for i in range(1,n):
        dp[i] = min(dp[i-j] + abs(h[i-j] - h[i]) for j in range(1,min(k,i)+1))
    print(dp[n-1])
main()
### BUGGY CODE ###

n,m=map(int,input().split())
mod=10**9+7
a=[]
dp=[0]*(n+1)
dp[0]=1
for i in range(m):
    a.append(int(input()))
if 1 in a:
    dp[1]=0
else:
    dp[1]=1
for j in range(2,n+1):
    if j not in a:
        dp[j]=dp[j-1]+dp[j-2]       
print(dp[n]%mod)            

    
    

### FIXED CODE ###

n,m=map(int,input().split())
mod=10**9+7
a=[0]*(n+1)
dp=[0]*(n+1)
dp[0]=1
for i in range(m):
    a[int(input())]=1
    
if a[1]==1:
    dp[1]=0
else:
    dp[1]=1
    
for j in range(2,n+1):
    if a[j]==0:
        dp[j]=dp[j-1]+dp[j-2] 
                  
print(dp[n]%mod)
### BUGGY CODE ###

def solve():
    N, a, b = map(int, input().split())
    
    MOD = 10 ** 9 + 7
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    
    # 必要なだけforを回す。N+1を書き換える
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)
    
    # nCr n個から重複を許さずr個の組み合わせを選ぶ
    def cmb(n, r):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return fact[n] * factinv[r] * factinv[n-r] % MOD
    
    ans = 0
    
    if N % 2 == 0:
        for i in range(1, N//2):
            ans += cmb(N, i) * 2 % MOD
        ans += 1
        ans += cmb(N, N//2) % MOD
        ans -= cmb(N, a) % MOD
        ans -= cmb(N, b) % MOD
    else:
        for i in range(1, N//2+1):
            ans += cmb(N, i) * 2 % MOD
        ans += 1
        ans -= cmb(N, a) % MOD
        ans -= cmb(N, b) % MOD

    return ans % MOD

print(solve())

### FIXED CODE ###

def solve():
    n, a, b = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    
    for i in range(2, max(a, b)+1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)
    
    def ncr(n, r):
        ret = factinv[r]
        for i in range(n, n-r, -1):
            ret = ret * i % MOD
        return ret
        
    ans = pow(2, n, MOD)
    ans = (ans-ncr(n, a)-ncr(n, b)-1) % MOD
    return ans


print(solve())
### BUGGY CODE ###

import numpy as np
n, m = map(int, input().split())
cards = np.zeros(n)
for _ in range(m):
    left, right = map(int, input().split())
    cards[left-1:right] += 1
print(len(cards[cards == m]))

### FIXED CODE ###

n, m = map(int, input().split())
left = []
right = []
for _ in range(m):
    l, r = map(int, input().split())
    left.append(l)
    right.append(r)
x = min(right) - max(left)
print(x+1) if x >=0 else print(0)
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    _max = max
    _min = min
    for _ in range(k):
        C = [0] * n
        for i in range(n):
            a = A[i]
            l = _max(0, i - a)
            r = _min(n, i + a + 1)
            C[l] += 1
            if r < n:
                C[r] -= 1
        r = 0
        for i in range(n):
            r += C[i]
            A[i] = r
    print(" ".join(map(str, A)))
main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    _max = max
    _min = min
    for _ in range(k):
        C = [0] * n
        i = 0
        for a in A:
            l = _max(0, i - a)
            r = _min(n, i + a + 1)
            C[l] += 1
            if r < n:
                C[r] -= 1
            i += 1
        r = 0
        for i in range(n):
            r += C[i]
            A[i] = r
        if A == [n] * n:
            break
    print(" ".join(map(str, A)))
main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range (0, N):
	if A[i] == 0:
		ans = 0
	else:
		ans *= A[i]

if ans > 10 ** 18:
	print(-1)
else:
	print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range (0, N):
	if A[i] == 0:
		ans = 0
		break
	else:
		if ans > 0:
			ans *= A[i]
		if ans > 10 ** 18:
			ans = -1

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

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

pt = []
G = [[None, 1] for x in range(N+1)]

def find(x):
    n = G[x]
    while not n[0] is None:
        n = n[0]
    return n

cnt = 0
while len(B):
    x, y = B.pop()
    wx = find(x)
    wy = find(y)
    if wx is wy:
        pt.append(0)
    else:
        pt.append(wx[1] * wy[1])
        wx[1] += wy[1]
        wy[0] = wx

    #print(G)

cnt = 0
while len(pt):
    cnt += pt.pop()
    print(cnt)


### FIXED CODE ###

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

pt = []
G = [[None, 1] for x in range(N+1)]

def find(x):
    n = G[x]
    c = []
    while not n[0] is None:
        c.append(n)
        n = n[0]
    for ci in c:
        ci[0] = n
    return n

cnt = 0
while len(B):
    x, y = B.pop()
    wx = find(x)
    wy = find(y)
    if wx is wy:
        pt.append(0)
    else:
        pt.append(wx[1] * wy[1])
        wx[1] += wy[1]
        wy[0] = wx

    #print(G)

cnt = 0
for _ in range(M):
    cnt += pt.pop()
    print(cnt)