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

from collections import deque
import itertools
import copy
import numpy as np

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

def solve(S, s):
    M = copy.deepcopy(S)
    d = [[1, 0], [-1, 0], [0, -1], [0, 1]]
    queue = deque([s])
    steps = [[-1 for _ in range(W)] for _ in range(H)]
    # steps = [[np.max for _ in range(W)] for _ in range(H)]
    # steps = [[H*W+1 for _ in range(W)] for _ in range(H)]
    steps[s[0]][s[1]] = 0

    while len(queue) > 0:
        current = queue.popleft()
        cy = current[0]
        cx = current[1]
        # if cy == g[0] and cx == g[1]:
        #     return steps[cy][cx]
        # else:
        M[cy][cx] = '#'
        for i in d:
            next = [cy+i[0], cx+i[1]]
            # はみ出さないかつ通ってない
            if (0<=next[0]<H and 0<=next[1]<W) and M[next[0]][next[1]]!='#':
                queue.append(next)
                steps[next[0]][next[1]] = steps[cy][cx] + 1
    # print(steps)
    # [i. for i in steps]
    # print(steps)
        
    return max([max(i) for i in steps])
# print(solve(S, [0, 0], [0, 1]))
# print(solve(S, [2, 0], [0, 4]))
# print(S)
maxStep = 0
for s in itertools.product(range(H), range(W)):
    if S[s[0]][s[1]] == '.':
        # print(s, g)
        # print(solve(S, [s[0], s[1]], [g[0], g[1]]))
        maxStep = max(solve(S, [s[0], s[1]]), maxStep)

print(maxStep)

### FIXED CODE ###

from collections import deque
import itertools
import copy

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

def solve(s):
    M = copy.deepcopy(S)
    d = ((1, 0), (-1, 0), (0, -1), (0, 1))
    queue = deque([s])
    steps = [[-1 for _ in range(W)] for _ in range(H)]
    steps[s[0]][s[1]] = 0

    while len(queue) > 0:
        current = queue.popleft()
        cy = current[0]
        cx = current[1]
        # M[cy][cx] = '#'
        for i in d:
            ny = cy+i[0]
            nx = cx+i[1]
            # はみ出さないかつ通ってない
            if (0<=ny<H and 0<=nx<W) and M[ny][nx]=='.' and steps[ny][nx] < 0:
            # if (0<=ny<H and 0<=nx<W) and M[ny][nx]!='#':
                queue.append([ny, nx])
                steps[ny][nx] = steps[cy][cx] + 1
        
    return max([max(i) for i in steps])

maxStep = 0
for s in itertools.product(range(H), range(W)):
    if S[s[0]][s[1]] == '.':
        maxStep = max(solve([s[0], s[1]]), maxStep)

print(maxStep)
### BUGGY CODE ###

from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m,d=zip(*eval('(input(),[I]*w),'*h))
q=deque([(s-1,t-1,1)])
while q:
 y,x,c=q.popleft()
 for i in range(y-2,y+3):
  for j in range(x-2,x+3):
   if h>i>-1<j<w<I==d[i][j]!=m[i][j]>'#':d[y][x]=c;abs(y-i)+abs(x-j)<2!=q.appendleft((i,j,c));q.append((i,j,c+1))
print(d[f-1][g-1]%I-1)

### FIXED CODE ###

from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m=[input()for _ in range(h)]
d=[[I]*w for _ in range(h)]
q=deque([(s-1,t-1,1)])
while q:
  y,x,c=q.popleft()
  if d[y][x]<I:continue
  d[y][x]=c
  for i,j in(y-1,x),(y,x-1),(y,x+1),(y+1,x):
    if h>i>-1<j<w<I==d[i][j]!=m[i][j]!='#':q.appendleft((i,j,c))
  for i,j in(y-2,x-2),(y-2,x-1),(y-2,x),(y-2,x+1),(y-2,x+2),(y-1,x-2),(y-1,x-1),(y-1,x+1),(y-1,x+2),(y,x-2),(y,x+2),(y+1,x-2),(y+1,x-1),(y+1,x+1),(y+1,x+2),(y+2,x-2),(y+2,x-1),(y+2,x),(y+2,x+1),(y+2,x+2):
    if h>i>-1<j<w<I==d[i][j]!=m[i][j]!='#':q.append((i,j,c+1))
print(d[f-1][g-1]%I-1)
### BUGGY CODE ###

A, B, K = map(int, input().split())

for i in range(A, B+1):
    if A <= i <= A+K-1 or B-K+1<= i <= B:
        print(i)

### FIXED CODE ###

A, B, K = map(int, input().split())

# for i in range(A, B+1):
#     if (A <= i and i <= A+K-1) or (B-K+1<= i and i <= B):
#         print(i)

S=set()

for i in range(A, min(B+1, A+K)):
    S.add(i)
for i in range(max(A, B-K+1), B+1):
    S.add(i)
for k in sorted(S):
    print(k)
### BUGGY CODE ###

N,C = map(int,input().split())
A = [[0 for _ in range(C)] for j in range(200001)]
for i in range(N):
    s,t,c = map(int,input().split())
    for j in range(s*2-1,t*2):
        A[j][c-1] = 1
R = 0
for i in range(200001):
    if R < sum(A[i]):
        R = sum(A[i])
print(R)


### FIXED CODE ###

N,C = map(int,input().split())
A = [[0 for _ in range(C)] for j in range(100001)]
for i in range(N):
    s,t,c = map(int,input().split())
    for j in range(s-1,t):
        A[j][c-1] = 1
R = 0
for i in range(100001):
    sumA = sum(A[i])
    if R < sumA:
        R = sumA
print(R)
### BUGGY CODE ###

n, q = map(int, input().split())
S = input()

for i in range(q):
  l, r = map(int, input().split())
  l = l-1
  r = r-1
  counter = 0
  for j in range(r - l):
    if S[l+j] == "A" and S[l+j+1] == "C":
      counter += 1
  print(counter)
    

### FIXED CODE ###

n, q = map(int, input().split())
S = input()

Sev = [0] * n
for i in range(n-1):
  if S[i] == "A" and S[i+1] == "C":
    Sev[i] = 1

Simos = [0] * n
Simos[0] = Sev[0]
for i in range(1, n):
  Simos[i] = Simos[i-1] + Sev[i]
    
for i in range(q):
  l, r = map(int, input().split())
  l = l-1
  r = r-1
  r = r-1
  if l == 0:
    print(Simos[r])
  else:
    print(Simos[r] - Simos[l-1])
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()
from collections import Counter
ans = 0
if P == 2 or P == 5:
    for i in range(N-1, -1, -1):
        t = S[i]
        if not int(t) % P:
            ans += i + 1
else:
    c = Counter()
    c[0] += 1
    p = 1
    t = int(S[N-1])
    c[t%P] += 1
    for i in range(N-2, -1, -1):
        p *= 10
        t = int(S[i]) * p + t
        c[t % P] += 1
    for a in c.values():
        ans += (a * (a-1)) // 2
print(ans)


### FIXED CODE ###

N, P = map(int, input().split())
S = input()
from collections import Counter
ans = 0
if P == 2 or P == 5:
    for i in range(N-1, -1, -1):
        t = S[i]
        if not int(t) % P:
            ans += i + 1
else:
    c = Counter()
    c[0] += 1
    p = 1
    t = int(S[N-1])
    c[t%P] += 1
    for i in range(N-2, -1, -1):
        p *= 10
        t = int(S[i]) * p + t
        c[t % P] += 1
        p %= P
    for a in c.values():
        ans += (a * (a-1)) // 2
print(ans)
### BUGGY CODE ###

from collections import deque

n = int(input())

to_battle_with = [deque([i - 1 for i in map(int, input().split())]) for _ in range(n)]

day_count = 0
remained_battles = (n * (n - 1)) // 2

while remained_battles:
    battled_today = set()

    no_battle_today = True
    for player in range(n):
        if not to_battle_with[player]:
            continue

        next_opponent = to_battle_with[player][0]
        if player in battled_today or next_opponent in battled_today:
            continue

        if not to_battle_with[next_opponent]:
            continue

        if to_battle_with[next_opponent][0] == player:
            battled_today.add(next_opponent)
            battled_today.add(player)
            to_battle_with[player].popleft()
            to_battle_with[next_opponent].popleft()
            remained_battles -= 1
            no_battle_today = False
    if no_battle_today:
        print(-1)
        break
    day_count += 1

if not no_battle_today:
    print(day_count)


### FIXED CODE ###

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

to_battle_with = [deque([i - 1 for i in map(int, input().split())]) for _ in range(n)]


def update_battle(player, battle_set, to_battle_with):
    if not to_battle_with[player]:
        return
    next_opponent = to_battle_with[player][0]
    if not to_battle_with[next_opponent]:
        return
    if to_battle_with[next_opponent][0] == player:
        if player > next_opponent:
            player, next_opponent = next_opponent, player
        battle_set.add((player, next_opponent))


battles_today = set()
for player in range(n):
    update_battle(player, battles_today, to_battle_with)

day_count = 0
battle_count = 0
num_all_battles = (n * (n - 1)) // 2

while battles_today:
    battles_tomorrow = set()
    for p1, p2 in battles_today:
        battle_count += 1
        to_battle_with[p1].popleft()
        to_battle_with[p2].popleft()
        for p in [p1, p2]:
            update_battle(p, battles_tomorrow, to_battle_with)
    battles_today = battles_tomorrow
    day_count += 1

if battle_count == num_all_battles:
    print(day_count)
else:
    print(-1)
### BUGGY CODE ###

n=int(input())
lists=[]
if n==1:
    print(0)
else:
    for _ in range(n-1):
        s=list(map(int,input().split()))
        lists.append(s)
        
    for x in range(n):
        nums=x+1
        #numsはどの駅から出発するかの駅の番号(1<=nums<=n)
        if nums==n:
            print(0)
        else:
            times=0
            while nums<n:
                if times>=lists[nums-1][1]:
                    while (times-lists[nums-1][1])%lists[nums-1][2]!=0:
                        times+=1
                    times+=lists[nums-1][0]
                    nums+=1
                    
                elif times<lists[nums-1][1]:
                    times=lists[nums-1][1]
                    times+=lists[nums-1][0]   
                    nums+=1
                    
            print(times)
            

### FIXED CODE ###

n=int(input())
lists=[list(map(int,input().split())) for _ in range(n-1)]  
for x in range(n):
    nums=x+1
    if nums==n:
        print(0)
    elif nums!=n:
        times=0
        while nums<n:
            if times>lists[nums-1][1]:
                if (times-lists[nums-1][1])%lists[nums-1][2]!=0:
                    a=(times-lists[nums-1][1])%lists[nums-1][2]  
                    times=times+lists[nums-1][2]-a
                    times+=lists[nums-1][0]
                    nums+=1  
                else:
                    times+=lists[nums-1][0]
                    nums+=1
            else:
                times=lists[nums-1][1]
                times+=lists[nums-1][0]   
                nums+=1 
        print(times)
### BUGGY CODE ###

A, B, Q = map(int, input().split())
s = [0]*A
for i in range(A):
    s[i] = int(input())
t = [0]*B
for i in range(B):
    t[i] = int(input())
x = [0]*Q
for i in range(Q):
    x[i] = int(input())

result = [0]*Q
c = 0
for k in x:
    cand = list()
    for sk in s:
        for tk in t:
            if abs(sk-k) < abs(tk-k):
                cand.append(abs(sk-k)+abs(sk-tk))
            else:
                cand.append(abs(tk - k) + abs(sk - tk))
    result[c] = min(cand)
    c += 1

for i in result:
    print(i)

### FIXED CODE ###

import bisect

A, B, Q = map(int, input().split())
s = [0]*A
for i in range(A):
    s[i] = int(input())
t = [0]*B
for i in range(B):
    t[i] = int(input())
X = [0]*Q
for i in range(Q):
    X[i] = int(input())

INF = 10 ** 18
s = [-INF] + s + [INF]
t = [-INF] + t + [INF]

for x in X:
    sr, tr = bisect.bisect_right(s, x), bisect.bisect_left(t, x)
    res = INF
    for S in [s[sr-1], s[sr]]:
        for T in [t[tr-1], t[tr]]:
            d1, d2 = abs(S-x)+abs(T-S), abs(T-x)+abs(S-T)
            res = min(res, d1, d2)
    print(res)
### BUGGY CODE ###

f = lambda:map(int,input().split())
n,m = f()
l = sorted(f())
for _ in range(m):
  l.append(l.pop()//2)
  l.sort()
print(sum(l))

### FIXED CODE ###

f = lambda:map(int,input().split())
_,m = f()
l = list(map(lambda x:-x,f()))
import heapq as hq
hq.heapify(l)
for i in range(m):
  p = -hq.heappop(l)//2
  hq.heappush(l,-p)
print(-sum(l))
### BUGGY CODE ###

import itertools

n, m, k = map(int, input().split())
a_books = [int(i) for i in input().split()]
b_books = [int(i) for i in input().split()]

#print(a_books)
data = ['a'] * n + ['b'] * m
all_lists = set()
for list in itertools.permutations(data):
  if list not in all_lists:
    all_lists.add(list)
#print(all_lists)
max_count = 0
for list in all_lists:
  count = 0
  a = 0
  b = 0
  time = 0
  for i in range(n+m):
    if list[i] == 'a':
      time += a_books[a]
      if time > k:
        break
      count += 1
      a += 1
    if list[i] == 'b':
      time += b_books[b]
      if time > k:
        break
      count += 1
      b += 1
  if count > max_count:
    max_count = count
  if max_count == n + m:
    break
print(max_count)


### FIXED CODE ###

n, m, k = map(int, input().split())
a_books = [int(i) for i in input().split()]
b_books = [int(i) for i in input().split()]

time = 0
count = 0
for i in range(n):
  time += a_books[i]
  if time > k:
    time -= a_books[i]
    i -= 1
    break
  count += 1
for j in range(m):
  time += b_books[j]
  if time > k:
    time -= b_books[j]
    j -= 1
    break
  count += 1
max_count = count
#print(max_count, time)
while j < m and i >= 0:
  time -= a_books[i]
  i -= 1
  count -= 1
  j += 1
  while j < m:
    time += b_books[j]
    if time > k:
      time -= b_books[j]
      j -= 1
      break
    count += 1
    j += 1
  if count > max_count:
    max_count = count
  #print(count, time)
  #print(max_count)
print(max_count)
### BUGGY CODE ###

n, m, k = map(int, input().split())
MOD = 998244353


def power(n, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 1:
        return (n * power(n, k - 1, mod)) % mod
    else:
        return power((n ** 2) % mod, k // 2, mod)


lp = {0: 1}  # (m - 1) ** i
p = 1
for i in range(n - 1):
    p = (p * (m - 1)) % MOD
    lp[i + 1] = p


lf = {0: 1}  # i!
f = 1
for i in range(n):
    f = (f * (i + 1)) % MOD
    lf[i + 1] = f

fn = lf[n - 1]


answer = 0

for i in range(k + 1):
    d = (lf[i] * lf[n - 1 - i]) % MOD
    dinv = power(d, MOD - 2, MOD)
    c = (fn * dinv) % MOD
    n_pattern = (c * m * lp[n - 1 - i]) % MOD

    answer = (answer + n_pattern) % MOD


# def n_pattern(n_pair):
#     return (lc[n_pair] * m * power(m - 1, n - 1 - n_pair, MOD)) % MOD


# answer = 0
# for i in range(k + 1):
#     answer = (answer + n_pattern(i)) % MOD


print(answer)






### FIXED CODE ###

n, m, k = map(int, input().split())
MOD = 998244353


class Combination:
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod

        self.f = self._get_f()
        self.fi = self._get_fi()

    def __call__(self, k):
        if not 0 <= k <= self.n:
            return 0
        else:
            num = self.f[self.n]
            deninv = (self.fi[k] * self.fi[self.n - k]) % self.mod
            return (num * deninv) % self.mod

    def _get_f(self):
        f = 1
        lf = [1]

        for i in range(1, self.n + 1):
            f = (f * i) % self.mod
            lf.append(f)

        return lf

    def _get_fi(self):
        ii = 1
        lii = [0, 1]  # [i^-1 modulo mod for i in 0, ..., n]
        fi = 1
        lfi = [1, 1]

        for i in range(2, self.n + 1):
            ii = (-lii[self.mod % i] * (self.mod // i)) % self.mod
            lii.append(ii)

            fi = (fi * ii) % self.mod
            lfi.append(fi)

        return lfi


c = Combination(n - 1, MOD)


def n_pattern(i):
    result = m
    result *= c(i)
    result %= MOD
    result *= pow(m - 1, n - i - 1, MOD)
    result %= MOD
    return result


answer = sum(n_pattern(i) for i in range(k + 1)) % MOD
print(answer)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(110000)

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

D = []

for _ in range(K):
    L, R = map(int, input().split())

    for i in range(L, R+1):
        D.append(i)


dp_memo = [-1] * 300000
dp_memo[1] = 1

def dp(v):
    if dp_memo[v] != -1:
        return dp_memo[v]
    ret = 0
    for d in D:
        if v - d < 1:continue
        ret += dp(v - d)
    ret %= 998244353
    dp_memo[v] = ret
    return ret

print(dp(N))

### FIXED CODE ###

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

L, R = [], []

for _ in range(K):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

dp = [0] * 300000
dpsum = [0] * 300000
dp[1] = 1
dpsum[1] = 1

for i in range(2, N+1):
    for j in range(K):
        li = min(L[j], i)
        ri = min(R[j], i + 1)
        dp[i] += dpsum[i - li] - dpsum[i - ri - 1]

    dp[i] %= 998244353
    dpsum[i] = dpsum[i-1] + dp[i]

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

import sys
sys.setrecursionlimit(10 ** 8)
INF = 10 ** 10

class edge:
    def __init__(self, fr, to, cost): self.fr, self.to, self.cost = fr, to, cost

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, M, P = ZZ()
    es = []
    for _ in range(M):
        a, b, c = ZZ()
        a -= 1
        b -= 1
        es.append(edge(a, b, -(c-P)))

    d = [INF] * N
    d[0] = 0
    for i in range(N-1):
        for e in es:
            if d[e.fr] != INF and d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
    n = [False] * N
    for i in range(N):
        for e in es:
            if d[e.fr] != INF and d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
                n[e.to] = True
            if n[e.fr] == True: n[e.to] = True
    print(-1 if n[N-1] else max(0, -d[N-1]))

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 8)
INF = 10 ** 10

class edge:
    def __init__(self, fr, to, cost): self.fr, self.to, self.cost = fr, to, cost

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, M, P = ZZ()
    es = []
    for _ in range(M):
        a, b, c = ZZ()
        a -= 1
        b -= 1
        es.append(edge(a, b, -(c-P)))

    d = [INF] * N
    d[0] = 0
    for i in range(N-1):
        for e in es:
            if d[e.fr] != INF and d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
    n = [False] * N
    for i in range(N):
        for e in es:
            if d[e.fr] != INF and d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
                n[e.to] = True
            if n[e.fr] == True: n[e.to] = True
    print(-1 if n[N-1] else max(0, -d[N-1]))

    return

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

from collections import Counter
ans = 0
s = []
N = int(input())
for i in range(N):
	tmp = []
	string = input()
	for st in string:
		tmp.append(st)
	s.append(tmp)

for m in s:
	for n in s:
		if Counter(n)==Counter(m) and m != n:
			ans+=1
print(int(ans/2))


### FIXED CODE ###

ans = 0
s = {}
N = int(input())
for i in range(N):
	tmp = []
	string = input()
	for st in string:
		tmp.append(st)
	tmp.sort()
	stmp = ''.join(tmp)
	if stmp in s and s[stmp] > 0:
		ans += s[stmp]
		s[stmp] = s[stmp]+1
	else:
		s[stmp] = 1
print(ans)
### BUGGY CODE ###

S = input()
listS = list(S)

for i in range(len(listS)):
	if listS[i] == "B":
		listS[i] = 0
	if listS[i] == "W":
		listS[i] = 1
		
done = False

x = 0
n = 0

while not done:
	for i in range(len(listS)-1):
		if listS[i] < listS[i+1]:
			listS[i] = 1
			listS[i+1] = 0
			x += 1
			n += 1

	if x == 0:
		print(n)
		done = True
	x = 0


### FIXED CODE ###

s = input()
s = list(s)


w_sum = 0
w_n = 0
for i, c in enumerate(s):
    if c == "W":
        w_sum += i
        w_n += 1
    
print(w_sum - w_n*(w_n-1)//2)
### BUGGY CODE ###

cardNum,gate = map(int,input().split())
lr = []
for i in range(gate):
  lr.append(list(map(int,input().split())))
okCard = 0
for card in range(1,cardNum+1):
  ok = True
  for check in lr:
    ok = ok and check[0] <= card <= check[1]
    if not ok:
      break
  if ok:
    okCard += 1
print(okCard)

### FIXED CODE ###

cardNum,gate = map(int,input().split())
l = []
r = []
for i in range(gate):
  ll,rr = map(int,input().split())
  l.append(ll)
  r.append(rr)

cnum = min(r)-max(l)+1
if cnum < 0:
  print(0)
else:
  print(cnum)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for i in range(q):
    l,r=map(int,input().split())
    print(s.count("AC",l-1,r))

### FIXED CODE ###

from collections import deque
n,q=map(int,input().split())
s=input()
AC=deque()
count=0
for i in range(n):
    if i!=0:
        if s[i-1:i+1]=="AC":
            count+=1
    AC.append(count)
for _ in range(q):
    l,r=map(int,input().split())
    print(AC[r-1]-AC[l-1])
### BUGGY CODE ###

N, W = map(int, input().split())
w_list = []
v_list = []
for _ in range(N):
  w, v = map(int, input().split())
  w_list.append(w)
  v_list.append(v)

w_list.insert(0,0)#アイテム番号を1インデックスに変更.
v_list.insert(0,0)#アイテム番号を1インデックスに変更.

INF = 10**12
dp = [[INF]*(max(v_list)*N+1) for _ in range(N+1)]
dp[0][0] = 0

#print(dp)

for i in range(1,N+1):
  for j in range(max(v_list)*N+1):
    #print(i,j)
    if j - v_list[i-1] >= 0:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-v_list[i]] + w_list[i])
    else:
      dp[i][j] = dp[i-1][j]
  #print(dp)


ans = 0
for j in range(max(v_list)*N+1):
  if dp[N][j] <= W:
    ans = max(ans, j)

print(ans)

### FIXED CODE ###

N, W = map(int, input().split())
w_list = []
v_list = []
for _ in range(N):
  w, v = map(int, input().split())
  w_list.append(w)
  v_list.append(v)

#w_list.insert(0,0)#アイテム番号を1インデックスに変更.
#v_list.insert(0,0)#アイテム番号を1インデックスに変更.

INF = 10**12
dp = [[INF]*(max(v_list)*N+1) for _ in range(N+1)]
dp[0][0] = 0

#print(dp)

for i in range(1,N+1):
  for j in range(max(v_list)*N+1):
    #print(i,j)
    if j - v_list[i-1] >= 0:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-v_list[i-1]] + w_list[i-1])
    else:
      dp[i][j] = dp[i-1][j]
  #print(dp)


ans = 0
for j in range(max(v_list)*N+1):
  if dp[N][j] <= W:
    ans = max(ans, j)

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

N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]


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

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

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 == s2:
            return
        if self.table[s1] >= self.table[s2]:
            self.table[s1] += self.table[s2]
            self.table[s2] = s1
        else:
            self.table[s2] += self.table[s1]
            self.table[s1] = s2


def main():
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.table[px] * uf.table[py]
            uf.union(px, py)
        ans.append(p)

    for a in reversed(ans[:-1]):
        print(a)


uf = UnionFind(N)
main()

### FIXED CODE ###

N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]


class UnionFind:
    def __init__(self,size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]

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

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]


def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.number[px] * uf.number[py]
            uf.union(px, py)
        ans.append(p)

    for a in reversed(ans[:-1]):
        print(a)


main()