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

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

w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

def func(N, W):
    dp = [0] * (W+1)
    for i in range(N):
        for j in range(W, w[i]-1, -1):
            a = dp[j-w[i]] + v[i]
            if dp[j] < a:
                dp[j] = a
    return dp[W]

print(func(N, W))

### FIXED CODE ###

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

dp = [0] * (W+1)
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
        a = dp[j-w]+v
        if dp[j] < a:
            dp[j] = a

print(dp[W])
### BUGGY CODE ###

import collections
import numpy as np

h, w, m = map(int, input().split())
lst_ = []
for i in range(m):
    h, m = map(int, input().split())
    lst_.append([h, m])

lst = np.array(lst_)
h_lst = collections.Counter(lst[:,0])
w_lst = collections.Counter(lst[:,1])

def get_cand(sub_lst):
    sub_lst = sub_lst.most_common()
    cand = []
    for sub in sub_lst:
        if sub[1] != sub_lst[0][1]:
            break
        cand.append(sub[0])
    return cand, sub_lst[0][1]

h_cand, h_count = get_cand(h_lst)
w_cand, w_count = get_cand(w_lst)

count = 0
for bomb in lst_:
    if bomb[0] in h_cand and bomb[1] in w_cand:
        count += 1

ans = h_count + w_count
if count < len(h_cand)*len(w_cand):
    print(ans)
else:
    print(ans-1)





### FIXED CODE ###

import collections
import numpy as np

h, w, m = map(int, input().split())
lst_ = []
h_lst = [0]*h
w_lst = [0]*w
for i in range(m):
    h_, w_ = map(int, input().split())
    lst_.append([h_, w_])
    h_lst[h_-1] += 1
    w_lst[w_-1] += 1

h_count = max(h_lst)
w_count = max(w_lst)
h_cand = set([i+1 for i, h_ in enumerate(h_lst) if h_ == h_count])
w_cand = set([i+1 for i, w_ in enumerate(w_lst) if w_ == w_count])
#print(h_cand, w_cand)

count = 0
for bomb in lst_:
    if bomb[0] in h_cand and bomb[1] in w_cand:
        count += 1

ans = max(h_lst) + max(w_lst)
if count < len(h_cand)*len(w_cand):
    print(ans)
else:
    print(ans-1)
### BUGGY CODE ###

mod = 10 ** 9 + 7
N = int(input())
A = [int(a) for a in input().split()]

# Nが偶数ならAiは全て奇数、Nが奇数なら Aiは全て偶数でなければならない,なぜなら、2x + Ai = N - 1を満たすxが自然数(非負整数)でなければならないから
# さらに、Nが奇数の時はfor i in range(0, N, 2) において 0が１個、それ以外のiが２個ずつ存在しなければならず(これはAiが全て偶数であることも満たしている)、
# Nが偶数の時はfor i in range(1, N, 2) において 全てのiが２個ずつ存在しなければならない(これはAiがすべて奇数であることも満たしている)
# これを踏まえた上でNが偶数の時は N/2人の位置が決まれば反対側の人の位置も決まり、Nが奇数の時は中央の人は固定として、それ以外 (N-1)/2人の位置が決まれば残りの人は反対側で位置が決まる。それぞれ２通りなので、
# よって
if N % 2 != 0:
    for i in range(0, N, 2):
        if A.count(i) == 2:
            continue
        elif A.count(0) == 1:
            continue
        print(0)
        exit()
    
    order_count = 1
    for i in range((N - 1) // 2):
        order_count = order_count * 2 % mod

else:
    for i in range(1, N, 2):
        if A.count(i) != 2:
            print(0)
            exit()
    order_count = 1
    for i in range(N // 2):
        order_count = order_count * 2 % mod

print(order_count)




### FIXED CODE ###

mod = 10 ** 9 + 7
N = int(input())
A = [int(a) for a in input().split()]
A.sort()

if N % 2 != 0:
    if A[0] == 0:
        for i in range(2, N, 2):
            if not (A[i] == i and A[i-1] == i):
                print(0)
                exit()
        order_count = 2 ** ((N - 1) // 2) % mod
    else:
        print(0)
        exit()

else:
    for i in range(1, N, 2):
        if not (A[i] == i and A[i-1] == i):
            print(0)
            exit()
    order_count = 2 ** (N // 2) % mod 

print(order_count)
### BUGGY CODE ###

N = int(input())
al = [[] for _ in range(N+1)]
for i in range(1,N+1):
    al[i] = int(input())
#print(al)

#初期値
n = 1
cnt = 1
visited = [0 for _ in range(N+1)]
visited[1] = 1
while al[n] != 2:
    cnt += 1
    n = al[n]
    if visited[n] == 1:
        print(-1)
        exit()
print(cnt)




### FIXED CODE ###

N = int(input())
al = [[] for _ in range(N+1)]
for i in range(1,N+1):
    al[i] = int(input())
#print(al)

#初期値
n = 1
cnt = 1
visited = [0 for _ in range(N+1)]
visited[1] = 1
while al[n] != 2:
    cnt += 1
    n = al[n]
    if visited[n] == 1:
        print(-1)
        exit()
    else:
        visited[n] = 1
print(cnt)
### BUGGY CODE ###

n, k, l = map(int, input().split())


class UnionFind():
    def __init__(self, N):
        self.rank = [0] * N
        self.par = [i for i in range(N)]

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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


uf1 = UnionFind(n)
uf2 = UnionFind(n)

rec = []
for i in range(k):
    p, q = map(int, input().split())
    uf1.unite(p - 1, q - 1)
    rec.append((p - 1, q - 1))

num = [1] * n
for i in range(l):
    r, s = map(int, input().split())
    uf2.unite(r - 1, s - 1)
    if (r - 1, s - 1) not in rec:
        rec.append((r - 1, s - 1))

for a, b in rec:
    if uf1.same(a, b) and uf2.same(a, b):
        num[a] += 1
        num[b] += 1


print(" ".join(map(str, num)))


### FIXED CODE ###

n, k, l = map(int, input().split())
from collections import defaultdict

class UnionFind( ):
    def __init__(self, N):
        self.rank = [0] * N
        self.par = [i for i in range(N)]

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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


uf1 = UnionFind(n)
uf2 = UnionFind(n)

for i in range(k):
    p, q = map(int, input().split())
    uf1.unite(p - 1, q - 1)


for i in range(l):
    r, s = map(int, input().split())
    uf2.unite(r - 1, s - 1)

pair = defaultdict(int)
for i in range(n):
    a = uf1.find(i)
    b = uf2.find(i)
    pair[(a, b)] += 1

ans = []
for i in range(n):
    ans.append(pair[(uf1.find(i), uf2.find(i))])

print(" ".join(map(str, ans)))
### BUGGY CODE ###

import numpy as np
from numba import jit
@jit(cache=True)

def solve(n,k,A):
    l,r=0,0
    for ki in range(k):
        B=np.zeros(n+1,dtype=int)
        for i,j in enumerate(A):
            l=max(0,i-j)
            r=min(n,i+j+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        np.delete(A,n-1)
    return A

n,k=map(int,input().split())
A=list(map(int,input().split()))
x=solve(n,k,A)
print(*x)
    

### FIXED CODE ###

import numpy as np
from numba import jit
@jit(cache = True)
def solve(n,k,A):
    l,r=0,0
    for i in range(k):
        B=np.zeros(n+1,dtype=np.int64)
        for x,y in enumerate(list(A)):
            l=max(0,x-y)
            r=min(n,x+y+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        if A[A==n].size==n:
            break
    return A
n,k=map(int,input().split())
a=list(map(int,input().split()))
A=np.array(a)
X=solve(n,k,A)
print(*X,sep=' ')
### BUGGY CODE ###

def calc(locate, start_point):
    if start_point <= min(locate):
        if locate[0] >= locate[shrine_no]: 
            print(locate[0] - start_point)
        else:
            print(locate[shrine_no] - start_point)
            
    elif start_point >= max(locate):
        if locate[shrine_no -1] >= locate[-1]:
            print(start_point - locate[-1])
        else:
            print(start_point - locate[shrine_no - 1])
            
    else:
        s_diff = start_point - locate[0]
        t_diff = start_point - locate[shrine_no]
        for i in range(1, shrine_no):
            if abs(s_diff) > abs(start_point - locate[i]):
                s_diff = start_point - locate[i]
                
        for i in range(shrine_no+1, shrine_no + temple_no):
            if abs(t_diff) > abs(start_point - locate[i]):
                t_diff = start_point - locate[i]
                
        if s_diff * t_diff < 0:
            s_diff_list = []
            t_diff_list = []
            
            for i in range(shrine_no):
                s_diff_list.append(start_point - locate[i])
            sort_s_diff = sorted(s_diff_list)
                
            for i in range(shrine_no, shrine_no + temple_no):
                t_diff_list.append(start_point - locate[i])
            sort_t_diff = sorted(t_diff_list)

            dist = []
            for i in range(len(s_diff_list)):
                for j in range(len(t_diff_list)):
                    dist.append(abs(s_diff_list[i]-t_diff_list[j]) + min(abs(s_diff_list[i]), abs(t_diff_list[j])))
            print(min(dist))
            
        elif s_diff * t_diff > 0:
            print(max(abs(s_diff), abs(t_diff)))
        else:
            print(abs(s_diff+t_diff))

shrine_no, temple_no, q = map(int, input().split())
locate = []
start = []

for i in range(shrine_no+temple_no+q):
    tmp = int(input())
    if i < shrine_no+temple_no:
        locate.append(tmp)
    else:
        start.append(tmp)

for i in range(len(start)):
    calc(locate, start[i])

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
loc = [int(input()) for i in range(Q)]
for i in range(len(loc)):
    x = loc[i]
    res = INF
    s_w, t_w = bisect.bisect_right(s,x), bisect.bisect_right(t,x)
    d1 = abs(s[s_w]-x) + abs(t[t_w]-s[s_w])
    d2 = abs(t[t_w]-x) + abs(s[s_w]-t[t_w])
    d3 = abs(s[s_w]-x) + abs(t[t_w-1]-s[s_w])
    d4 = abs(t[t_w-1]-x) + abs(t[t_w-1]-s[s_w])
    d5 = abs(s[s_w-1]-x) + abs(t[t_w]-s[s_w-1])
    d6 = abs(t[t_w]-x) + abs(s[s_w-1]-t[t_w])
    d7 = abs(s[s_w-1]-x) + abs(t[t_w-1]-s[s_w-1])
    d8 = abs(t[t_w-1]-x) + abs(s[s_w-1]-t[t_w-1])
    print(min(d1,d2,d3,d4,d5,d6,d7,d8))
### BUGGY CODE ###

from queue import PriorityQueue


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_sum = sum(A)
B_sum = sum(B)
diff = B_sum - A_sum
if diff < 0:
    print("No")
    exit()

Aq = PriorityQueue()
Bq = PriorityQueue()
for a in A:
    Aq.put((a, a))
for b in B:
    Bq.put((b, b))

cnt = 0

while cnt <= diff and (not Aq.empty()) and (not Bq.empty()):
    _, a = Aq.get()
    _, b = Bq.get()
    if a < b:
        ne_a = a + 2
        ne_b = b + 1
        Aq.put((ne_a, ne_a))
        Bq.put((ne_b, ne_b))
        cnt += 1

if Aq.empty() and Bq.empty():
    print("Yes")
else:
    print("No")


### FIXED CODE ###

import math
from queue import PriorityQueue


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_sum = sum(A)
B_sum = sum(B)
diff = B_sum - A_sum
if diff < 0:
    print("No")
    exit()

cnt = 0
for a, b in zip(A, B):
    if a < b:
        cnt += math.ceil((b - a) / 2)

if cnt > diff:
    print("No")
else:
    print("Yes")
### BUGGY CODE ###

N = int(input())
array = list(map(int, input().split()))
sameNum = [0]*(N)

for i in range(N):
    sameNum[array[i]-1] += 1

for k in range(1, N+1):
    answer = 0
    sameNumT = sameNum.copy()
    sameNumT[array[k-1]-1] -= 1
    for l in range(N):
        answer += sameNumT[l]*(sameNumT[l]-1)//2
    print(answer)

### FIXED CODE ###

N = int(input())
array = list(map(int, input().split()))
sameNum = [0]*(N)
sum = 0
# kを削除していないlistでの組み合わせを調べる
for i in range(N):
    sameNum[array[i]-1] += 1
for i in range(N):
    sum += sameNum[i]*(sameNum[i]-1)//2

for k in range(1, N+1):
    sumT = sum
    print(sumT - sameNum[array[k-1]-1] + 1)
### BUGGY CODE ###

S=input()
count=0
while True:
    S=S.replace("01","z")
    S=S.replace("10","z")
    count+=S.count("z")*2
    if S.count("z")==0:
        print(count)
        break
    S=S.replace("z","")

### FIXED CODE ###

S=input()
count=0
o=S.count("1")
z=S.count("0")
if o>=z:
    print(z*2)
else:
    print(o*2)
### BUGGY CODE ###

n, K = map(int, input().split())
point = []
x_list = []
y_list = []
for _ in range(n):
    x, y = map(int, input().split())
    point.append((x, y))
    x_list.append(x)
    y_list.append(y)
x_list.sort()
y_list.sort()

ans = 4 * (10 ** 18)
for i in range(len(x_list)):
    for j in range(i + 1, len(x_list)):
        for k in range(len(y_list)):
            for l in range(k + 1, len(y_list)):
                num = 0
                for x, y in point:
                    if (x_list[i] <= x <= x_list[j]) & (y_list[k] <= y <= y_list[l]):
                        num += 1
                if num >= K:
                    ans = min(ans, abs((x_list[j] - x_list[i]) * (y_list[l] - y_list[k])))
print(ans)

### FIXED CODE ###

n, K = map(int, input().split())
point = []
x_list = []
y_list = []
for _ in range(n):
    x, y = map(int, input().split())
    point.append((x, y))
    x_list.append(x)
    y_list.append(y)
x_list.sort()
y_list.sort()

ans = 4 * (10 ** 18)
for i in range(len(x_list)):
    for j in range(i + 1, len(x_list)):
        for k in range(len(y_list)):
            for l in range(k + 1, len(y_list)):
                num = 0
                for x, y in point:
                    if (x_list[i] <= x <= x_list[j]) & (y_list[k] <= y <= y_list[l]):
                        num += 1
                if num >= K:
                    ans = min(ans, abs((x_list[j] - x_list[i]) * (y_list[l] - y_list[k])))
print(ans)
### BUGGY CODE ###

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

res = 0
sorted_lengths = sorted(lengths)[::-1]
for i in range(n):
	l1 = sorted_lengths[i]
	for j in range(i+1, n):
		l2 = sorted_lengths[j]
		res += sum([l1 - l2 < _ < l1 + l2 for _ in sorted_lengths[j + 1:]])
		
print(res)


### FIXED CODE ###

from bisect import bisect_left

n = int(input())
lengths = sorted(map(int, input().split()))

res = 0
for i in range(n):
	l1 = lengths[i]
	for j in range(i + 1, n - 1):
		l2 = lengths[j]
		res += bisect_left(lengths, l1 + l2, j + 1) - j - 1

print(res)
### BUGGY CODE ###

x = int(input())
flg = 0
_flg = 1
while flg == 0:
    mx  = int(x**0.5)
    for i in range(2, mx+1):
        if x % i == 0:
            _flg = 0
            break
    fig = _flg
    if flg == 0:
        x+=1
print(x)


### FIXED CODE ###

def com(_x):
    _flg = 1
    mx  = int(_x**0.5)
    for i in range(2, mx+1):
        if _x % i == 0:
            _flg = 0
            break
    return _flg


def main():
    x = int(input())
    flg = 0
    while flg == 0:
        #print("a")
        flg = com(x)
        if flg == 0:
            x+=1
    print(x)



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

n, q = list(map(int, input().split()))
s = input().split()[0]
lr_list = []
lr_list = [list(map(int, input().split())) for _ in range(q)]

count_ac_list = []
for i in range(n):
    count_ac_list.append(s[:i+1].count('AC'))

# print(count_ac_list)
count_list = [str(count_ac_list[r-1] - count_ac_list[l-1])
    if l > 1 else str(count_ac_list[r-1])
    for l, r in lr_list]

print('\n'.join(count_list))


### FIXED CODE ###

n, q = list(map(int, input().split()))
s = input().split()[0]
lr_list = [list(map(int, input().split())) for _ in range(q)]

count_ac_list = [0] * n
for i in range(n-1):
    # print('{}: {}'.format(i, s[i:i+2]))
    if s[i:i+2] == 'AC':
        count_ac_list[i+1] = count_ac_list[i] + 1
    else:
        count_ac_list[i+1] = count_ac_list[i]

count_list = [str(count_ac_list[r-1] - count_ac_list[l-1]) for l, r in lr_list]

print('\n'.join(count_list))
### BUGGY CODE ###

from  fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)

MOD = int(1e9 + 7)

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

LCM = 1

for i in range(N):
    LCM = lcm(LCM, A[i])
ans = 0
for i in range(N):
    ans += LCM * pow(A[i], MOD - 2, MOD)
    ans %= MOD
print(ans)

### FIXED CODE ###

def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor:GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)
def lcm(x, y):
    return (x * y) // gcd(x, y)

MOD = int(1e9 + 7)

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

LCM = 1

for i in range(N):
    LCM = lcm(LCM, A[i])
ans = 0
for i in range(N):
    ans += LCM * pow(A[i], MOD - 2, MOD)
print(ans%MOD)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
#dp[i] をiまでの最小コスト
INF = 10**9
h.extend([INF for i in range(100)])
dp = [INF for i in range(N+100)]
dp[0] = 0
for i in range(N):
    for k in range(1,K+1):
        dp[i + k] = min(dp[i + k], dp[i] + abs(h[i+k] - h[i])) # i => i+k でのコストの更新
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
#dp[i] をiまでの最小コスト
INF = 10**9
# h.extend([INF for i in range(100)])
dp = [INF for i in range(N)]
dp[0] = 0
for i in range(N):
    for k in range(1,K+1):
        if i + k >= N:
            break
        dp[i + k] = min(dp[i + k], dp[i] + abs(h[i+k] - h[i])) # i => i+k でのコストの更新
print(dp[N-1])
### BUGGY CODE ###

n ,m = map(int,input().split())
s = set()
for i in range(m):
    l,r = map(int, input().split())
    tmp = {i for i in range(l,r+1)}
    if not s:
        s = s | tmp
        continue
    s = s&tmp
print(len(s))

### FIXED CODE ###

n ,m = map(int,input().split())
ll = 1
rr = n
for i in range(m):
    l,r = map(int, input().split())
    if l > ll:
        ll = l
    if r < rr:
        rr = r
ans = rr - ll +1
if ans > 0:
    print(ans)
else:
    print(0)
### BUGGY CODE ###

import functools
mod=10**9+7

def f(A):
 dem=functools.reduce(lambda x,y:x*y,range(n,n-A,-1))
 num=functools.reduce(lambda x,y:x*y,range(1,A+1))
 return dem*pow(num,mod-2,mod)%mod

stdin=open(0)
n,a,b=map(int,stdin.read().split())
ans=pow(2,n,mod)-f(a)-f(b)-1
ans%=mod
print(ans)

### FIXED CODE ###

mod=10**9+7
n,a,b=map(int,input().split())
ans=pow(2,n,mod)-1 #n種類の花を使って花束を作る総数は2^n-1通り
comb1=1 #nCaの計算
for i in range(n-a+1,n+1): #n*(n-1)*…*(n-a+1)を計算
 comb1*=i
 comb1%=mod
for i in range(1,a+1): #1/a!=1/(1*2*…*a)=1^(p-2)*2^(p-2)*…*a^(p-2) (p=10**9+7)を計算
 comb1*=pow(i,mod-2,mod)
 comb1%=mod
comb2=1
for i in range(n-b+1,n+1): #n*(n-1)*…*(n-b+1)を計算
 comb2*=i
 comb2%=mod
for i in range(1,b+1): #1/b!=1/(1*2*…*b)=1^(p-2)*2^(p-2)*…*b^(p-2) (p=10**9+7)を計算
 comb2*=pow(i,mod-2,mod)
 comb2%=mod
ans-=(comb1+comb2) #nCa、nCbを総数から引く
ans%=mod
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split(' '))
H_ls = list(map(int, input().split(' ')))
AB_ls, cnt = [], 0
for i in range(M):
    AB_ls.append(list(map(int, input().split(' '))))
for i in range(N):
    val = H_ls[i]
    is_peak = True
    for s in AB_ls:
        ls = []
        if (i + 1) in s:
            [ ls.append(x) for x in s if x != (i + 1)]
            if val <= H_ls[ls[0] - 1]:
                is_peak = False
                break
    if is_peak:
        cnt += 1
print(cnt)

### FIXED CODE ###


N, M = map(int, input().split(' '))
H_ls = list(map(int, input().split(' ')))
edge = [ [] for i in range(N)]
cnt = 0
for i in range(M):
    a, b = map(int, input().split(' '))
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
for i in range(N):
    is_peak = True
    for neighbor in edge[i]:
        if H_ls[i] <= H_ls[neighbor]:
            is_peak = False
            break
    if is_peak:
        cnt += 1
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    A = LI()
    A.sort()
    MAX = 10**6+1
    All = [0 for i in range(MAX)]

    setA = set(A)
    for i in A:
        k = i
        while k < MAX:
            All[k] += 1
            k += i

    ans = 0
    for i in A:
        if All[i] == 1:
            ans += 1

    print(ans)

    # oj t -c "pypy3 main.py"
    # acc s main.py -- --guess-python-interpreter pypy
main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    A = LI()
    A.sort()
    MAX = A[-1]+1
    All = [0 for i in range(MAX)]

    setA = set(A)
    for i in A:
        k = i
        All[k] += 1
        k += i
        if All[i] == 2:
            continue
        while k < MAX and i in setA:
            All[k] += 1
            k += i

    ans = 0
    for i in range(1, MAX):
        if All[i] == 1 and i in setA:
            ans += 1

    print(ans)

    # oj t -c "pypy3 main.py"
    # acc s main.py -- --guess-python-interpreter pypy
main()
### BUGGY CODE ###


N, M = map(int, input().split())
adj = [[] for i in range(N)]
ng = [[] for i in range(N)]

ninp = []

for i in range(M):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  adj[x].append(y)
  adj[y].append(x)
  ninp.append((x, y))

def search():
  edges = [[None for i in range(N)] for j in range(N)]

  def dfs(u, f):
    stack = [u]
    colors = ["white"] * N

    while stack:
      u = stack.pop()
      colors[u] = "black"
      edges[f][u] = 0

      for v in list(filter(lambda x: colors[x] != "black" and not x in ng[u], adj[u])):
        stack.append(v)
        colors[v] = "gray"

  for u in range(N):
    dfs(u, u)

  ans = 0
  
  for n in range(N):
    for m in range(n, N):
      if edges[n][m] == None:
        ans += 1
  print(ans)

for (x, y) in ninp:
  ng[x].append(y)
  ng[y].append(x)
  search()



### FIXED CODE ###

# TLEしない適切な解法を思いつけず

class UnionFind:

  def __init__(self, n):
    self.parents = [-1] * n

  def find(self, n):
    if self.parents[n] < 0:
      return n

    self.parents[n] = self.find(self.parents[n])
    return self.parents[n]

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

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
      x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def size(self, x):
    return -self.parents[self.find(x)]

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


N, M = map(int, input().split())
edges = []

for i in range(M):
  x, y = map(int, input().split())
  edges.append((x,y))

uf = UnionFind(N)

ans = [N * (N-1) // 2]

for i in range(M-1, 0, -1):
  x, y = edges[i]
  x -= 1
  y -= 1
  if not uf.is_same(x, y):
    ans.append(ans[-1] - uf.size(x) * uf.size(y))
    uf.union(x, y)
  else:
    ans.append(ans[-1])
    
for a in ans[::-1]:
  print(a)