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

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

A=[]
B=[]

for _ in range(M):
  n, m = map(int, input().split())
  A.append(n)
  B.append(m)

roomN = ['N' for _ in range(N)]
roomN[0] = 1
roomPN = [0 for _ in range(N)]

for order in range(2, N+1):
  if not 'N' in roomN:
    break
  if order-1 in roomN:
     pres = [i+1 for i,x in enumerate(roomN) if x == order-1]
  for pre in pres:
    if pre in A:
      indexs = [i for i,x in enumerate(A) if x == pre]
      for index in indexs:
        now = B[index] -1
        if roomN[now] == 'N':
          roomN[now] = order
          if roomPN[now] == 0:
            roomPN[now] = pre
    if pre in B:
      indexs = [i for i,x in enumerate(B) if x == pre]
      for index in indexs:
        now = A[index] -1
        if roomN[now] == 'N':
          roomN[now] = order
          if roomPN[now] == 0:
            roomPN[now] = pre

print('Yes')
for i in range(1, N):
  print(roomPN[i])

### FIXED CODE ###

from collections import deque

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

graph=[[] for i in range(n)]

roomSign=[-1]*n

for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)

D=deque([0])

while D:
    v=D.popleft()
    for i in graph[v]:
        if roomSign[i] == -1:
          roomSign[i]=v
          D.append(i)

print("Yes")

for i in range(1,n):
    print(roomSign[i]+1)
### BUGGY CODE ###

n = int(input())
d = dict()
a = [ int(i) for i in input().split() ]

for i in range(n):
    for j in range(1,int(a[i]**0.5)+1):
        if a[i] % j == 0:
            try:
                d[j].add(i)
            except:
                d[j] = set()
                d[j].add(i)
            try:
                d[a[i]//j].add(i)
            except:
                d[a[i]//j] = set()
                d[a[i]//j].add(i)

ans = 0
for i in d.keys():
    if len(d[i]) >= n-1:
        ans = max(ans, i)
print(ans)


### FIXED CODE ###

n = int(input())
d = set()
a = [ int(i) for i in input().split() ]
a = sorted(a)
for i in range(2):
    for j in range(1,int(a[i]**0.5)+1):
        if a[i] % j == 0:
            d.add(j)
            d.add(a[i]//j)
ans = 0
for i in d:
    cnt = 0
    for j in a:
        if j % i != 0:
            cnt += 1

        if cnt >= 2:
            break

    if cnt < 2:
        ans = max(ans,i)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
# ワーシャルフロイド+全探索

import numpy as np
import itertools

def main():
    N, M, R = map(int, input().split())
    rs = map(int, input().split())
    graph = np.zeros((N, N))
    
    # グラフ作る
    for _ in range(M):
        a, b, c = map(int, input().split())
        graph[a-1, b-1] = c
        graph[b-1, a-1] = c
    
    # ワーシャルフロイドで全頂点間距離算出
    cost = np.zeros((N, N))
    for i in range(N):
        for j in range(N):
            if i==j:
                cost[i, j] = 0
                cost[j, i] = 0
            elif graph[i, j] == 0:
                cost[i, j] = float('inf')
            else:
                cost[i, j] = graph[i, j]
    for k in range(N):
        for i in range(N):
            for j in range(N):
                cost[i, j] = min(cost[i, j], cost[i, k] + cost[k, j])

    # 組み合わせ全探索
    ans = float('inf')
    for route in itertools.permutations(rs, R):
        d = 0
        for i in range(len(route)-1):
            d += cost[route[i]-1, route[i+1]-1]
        ans = min(ans, d)
    
    print(int(ans))


if __name__=='__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python
# ワーシャルフロイド+全探索

import numpy as np
import itertools

def main():
    N, M, R = map(int, input().split())
    rs = list(map(int, input().split()))
    inf = float('inf')
    cost = [[inf]*N for _ in range(N)]

    # グラフ作る
    for i in range(N):
        cost[i][i] = 0

    for _ in range(M):
        a, b, c = map(int, input().split())
        cost[a-1][b-1] = c
        cost[b-1][a-1] = c
    
    # ワーシャルフロイドで全頂点間距離算出
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if cost[i][k]+cost[k][j] < cost[i][j]:
                    cost[i][j] = cost[i][k] + cost[k][j]

    # 組み合わせ全探索
    ans = inf
    for route in itertools.permutations(rs):
        d = 0
        for i in range(R-1):
            d += cost[route[i]-1][route[i+1]-1]
            if d > ans:
                break
        ans = min(ans, d)
    
    print(int(ans))


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

N = int(input())
count = 0
def make_divisors(n):
    count = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            count += 1
            if i != n // i:
                count += 1
    return count
for X in range(N):
  count += make_divisors(X)
print(count)
  

### FIXED CODE ###

N = int(input())
ans = 0
for A in range(1,N):
  ans += (N-1) // A
print(ans)
### BUGGY CODE ###

H, W, M = list(map(int, input().split()))
hrz = [0]*H
vrt = [0]*W
targets = set()
for _ in range(M):
    h, w = list(map(lambda x: int(x) - 1, input().split()))
    targets.add((h, w))
    hrz[h] += 1
    vrt[w] += 1

hrz_max = max(hrz)
vrt_max = max(vrt)
for h in [i for i in range(H) if hrz[i] == hrz_max]:
    for w in [i for i in range(W) if vrt[i] == vrt_max]:
        if not (h, w) in targets:
            print(hrz_max+vrt_max)
            exit()
print(hrz_max+vrt_max-1)


### FIXED CODE ###

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

targets = set()
row = [0]*H
col = [0]*W

for _ in range(M):
    h, w = list(map(lambda x: int(x) - 1, input().split()))
    row[h] += 1
    col[w] += 1
    targets.add((h, w))

r_max = max(row)
c_max = max(col)
ans = 0

maxed_h = set([h for h in range(H) if row[h] == r_max])
maxed_w = set([w for w in range(W) if col[w] == c_max])
bomb_option_sites_n = len(maxed_h)*len(maxed_w)
targets_on_bomb_option = 0
for th, tw in targets:
    if th in maxed_h and tw in maxed_w:
        targets_on_bomb_option += 1

if bomb_option_sites_n == targets_on_bomb_option:
    print(r_max + c_max - 1)
else:
    print(r_max + c_max)
### BUGGY CODE ###

from fractions import Fraction


def comb(n: int, k: int) -> int:
    if n < 0 or k < 0:
        pdt = 0
    else:
        pdt = 1
        for s in range(1, k + 1):
            pdt *= Fraction(n - s + 1, s)

    return pdt.numerator


N = int(input())

dic = {}
for i in range(N):
    s = sorted(input())
    s = "".join(s)
    dic.setdefault(s, 0)
    dic[s] += 1

ans = 0
for value in dic.values():
    ans += comb(value, 2)
print(ans)


### FIXED CODE ###

from fractions import Fraction


def comb(n: int, k: int) -> int:
    if n < 0 or k < 0:
        pdt = 0
    else:
        pdt = 1
        for s in range(1, k + 1):
            pdt *= Fraction(n - s + 1, s)

    return pdt.numerator


N = int(input())

dic = {}
for i in range(N):
    s = sorted(input())
    s = "".join(s)
    dic.setdefault(s, 0)
    dic[s] += 1

ans = 0
for value in dic.values():
    ans += comb(value, 2)
print(ans)
### BUGGY CODE ###

# encoding: "utf-8"

class Stdin:
    @staticmethod
    def read_line(converter=str):
        return [converter(x) for x in input().split()]
    
    @staticmethod
    def read_lines(n, converter=str):
        result = list()
        for _ in range(n):
            result.append(Stdin.read_line(converter))
        return result
    
    @staticmethod
    def convert(data, converter):
        assert(len(data) == len(converter))
        return tuple(map(lambda x, f: f(x), data, converter))

    @staticmethod
    def convert_lines(datas, n, converter):
        return [converter(data, n, converter) for data in datas]


def main():
    _ = input()
    xs = Stdin.read_line(converter=int)
    xs.sort()
    ys = {i: xs.count(i) for i in set(xs)}
    m = 0
    for x in ys.keys():
        temp = ys.get(x-1, 0) + ys.get(x, 0) + ys.get(x+1, 0)
        if m < temp:
            m = temp
    print(m)

if __name__ == "__main__":
    main()

### FIXED CODE ###

input()
a_list = [int(s) for s in input().split()]

count = [0]*100002

for a in a_list:
    count[a] += 1
    count[a+1] += 1
    count[a+2] += 1
    
print(max(count))
### BUGGY CODE ###

#sys.stdin.readline()
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
P = []
Y = []
P_Y = [[]*N for _ in range(N)]

for i in range(M):
  p,y = map(int,input().split())
  P.append(p-1)
  Y.append(y)
  P_Y[p-1].append(y)
  
for i in range(N):
 P_Y[i].sort()

for i in range(M):
  ID1 = "{0:06d}".format(P[i]+1)
  tmp = P_Y[P[i]].index(Y[i])
  ID2 = "{0:06d}".format(tmp + 1)
  print(ID1 + ID2)

### FIXED CODE ###

N, M = map(int, input().split())
P_Y = []
for i in range(M):
   p,y = map(int,input().split())
   P_Y.append([p-1,y,i])
#n次元リストのソート
#普通にsort()をつけると1番目の要素でソート
#1番目の要素が同じ場合は2番目の要素の大小によってソートされる
P_Y.sort() 

ans_P_Y = [] 
count = 1
for i in range(M):
  if(i != 0):
    if(P_Y[i-1][0] == P_Y[i][0]): count += 1
    else: count = 1
  ans_P_Y.append([P_Y[i][2],P_Y[i][0]+1,count])
ans_P_Y.sort()

for i in range(M):
  ans = str(ans_P_Y[i][1]).zfill(6) + str(ans_P_Y[i][2]).zfill(6)
  print(ans)
### BUGGY CODE ###

n = int(input())
a = []
for _ in range(n):
    c0, c1 = map(int, input().split())
    a.append([c0-c1, c0+c1])
a.sort(key=lambda x: x[1])
ans = 1
b = [a[0]]

for i in a[1:]:
    for j, k in enumerate(b):
        if not (k[1] <= i[0]):
            break
        if j == len(b)-1:
            ans += 1
            b.append(i)
print(ans)


### FIXED CODE ###

n = int(input())
a = []
for _ in range(n):
    c0, c1 = map(int, input().split())
    a.append([c0-c1, c0+c1])
a.sort(key=lambda x: x[1])
ans, b = 1, a[0][1]
for i in a[1:]:
    if b <= i[0]:
        b = i[1]
        ans += 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
# from math import gcd

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

def solve(A: int, B: int):
    a = gcd(A,B)
    ap = a
    ct = 0
    x = 2
    if a % x == 0:
        ct+=1
        while a % x == 0:
            a = a // x
    x = 3
    while x < a+1: 
        if a % x == 0:
            ct+=1
            while a % x == 0:
                a = a // x
        x+=2
    # print(pa)

    print(ct+1)
    
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# from math import gcd

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

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# print(factorization(14)) 

def solve(A: int, B: int):
    a = gcd(A,B)
    ap = a
    ct = 0
    x = 2
    if a % x == 0:
        ct+=1
        while a % x == 0:
            a = a // x
    x = 3
    while x*x < ap+1: 
        if a % x == 0:
            ct+=1
            while a % x == 0:
                a = a // x
        x+=2
    # print(pa)
    if a != 1:
        ct +=1
    print(ct+1)
    
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

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

S=input()[::-1]
l=len(S)
t=0
p=0

ss=[0]*2019
ss[0]=1
d=1
for i in S:
    p=(p+int(i)*d)%2019
    d*=10
    ss[p]+=1

for c in ss:
    t+=c*(c-1)//2
print(t)


### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

## a, bを無向辺として，隣接リストを作成
N, Q = list(map(int, input().split()))
al = [[] for i in range(N)]

for i in range(N-1):
    a, b = list(map(int, input().split()))

    al[a-1].append(b-1)
    al[b-1].append(a-1)

visited = [0 for i in range(N)]
seen = [0 for i in range(N)]
score = [0 for i in range(N)]

for i in range(Q):
    p, x = map(int, input().split())
    score[p-1] += x

@functools.lru_cache(None)
def dfs_rec(u):
    visited[u] = 1
    for v in al[u]:
        if visited[v] == 0:
            score[v] += score[u]
            dfs_rec(v)

dfs_rec(0)

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

### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

## a, bを無向辺として，隣接リストを作成
N, Q = list(map(int, input().split()))
al = [[] for i in range(N)]

for i in range(N-1):
    a, b = list(map(int, input().split()))

    al[a-1].append(b-1)
    al[b-1].append(a-1)

visited = [0 for i in range(N)]
seen = [0 for i in range(N)]
score = [0 for i in range(N)]

for i in range(Q):
    p, x = map(int, input().split())
    score[p-1] += x

@functools.lru_cache(None)
def dfs_rec(u):
    visited[u] = 1
    for v in al[u]:
        if visited[v] == 0:
            score[v] += score[u]
            dfs_rec(v)

dfs_rec(0)

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

N,K = map(int,input().split())
S = []
for _ in range(K):
    l,r = map(int,input().split())
    S+=[i for i in range(l,r+1)]
    S.sort()

dp=[0]*(N+1)
dp[1]=1

for i in range(2,N+1):
    for j in S:
        if i<j:
            break
        else:
            dp[i]+=dp[i-j]
#print(S)
#print(dp)
print(dp[-1]%998244353)

### FIXED CODE ###

N,K = map(int,input().split())
S = [tuple(map(int,input().split())) for _ in range(K)]
MOD=998244353
dp=[0]*N
dp[0]=1
for i in range(N-1):
    x = dp[i]
    dp[0]=0
    for k in range(K):
        l,r = S[k]
        if i+l < N:
            dp[i+l]+=x
            dp[i+l]%=MOD
        if i+r+1 < N:
            dp[i+r+1]-=x
            dp[i+r+1]%=MOD
    dp[i+1]+=dp[i]
    dp[i+1]%=MOD
print(dp[-1]%MOD)
### BUGGY CODE ###

import math
import itertools
import statistics
#n = int(input())
#n, d = list(input().split())
N = int(input())
X = list(map(int, input().split()))
tmp = 0

for i in range(N):
    tmp = X[i]
    X[i]=0
    print(statistics.median_high(X))
    X[i]=tmp


### FIXED CODE ###

import itertools
import statistics
#n = int(input())
#n, d = list(input().split())
N = int(input())
X = list(map(int, input().split()))
sortedX = sorted(X)
mid_min = sortedX[N//2-1]
mid_max = sortedX[N//2]

for i in X:
    if i <= mid_min:
        print(mid_max)
    else:
        print(mid_min)
### BUGGY CODE ###

import itertools

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

ans = 0
for pair in itertools.combinations(A, 2):
    ans += pair[0] * pair[1]
    ans = ans % (10**9+7)

print(ans)


### FIXED CODE ###

'''
（公式解説参照）
A[i]*A[i+1]+A[i]*A[i+2]+…+A[i]*A[N]=A[i]*(A[i+1]+A[i+2]+…+A[N])
リストAに対する累積和を求めておく
'''
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

# 累積和
total = []
total.append(A[0])
for i in range(1, N):
    total.append(total[i-1] + A[i])
# print(total)

# iの値について全探索
ans = 0
for i in range(N):
    tmp = (total[-1] - total[i])
    ans += A[i] * tmp
    ans %= MOD

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

import sys
sys.setrecursionlimit(10 ** 7)
N,Q =  map(int,input().split())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

val = [0 for i in range(N)]
for i in range(Q):
    a,b = map(int,input().split())
    val[a-1] += b 
visited = [True for i in range(N)]

def dps(i): 
    visited[i] = False
    for j in graph[i]:
        if visited[j]:
            val[j] += val[i]
            dps(j)
                
dps(0)
for i in val:
    print(i,end=" ")
    

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
readline = sys.stdin.readline
N,Q =  map(int,input().split())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,readline().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

val = [0 for i in range(N)]
for i in range(Q):
    a,b = map(int,readline().split())
    val[a-1] += b 

def dps(i,parent): 
    for j in graph[i]:
        if j == parent:
            continue
        val[j] += val[i]
        dps(j,i)
                
dps(0,-1)
print(*val)
### BUGGY CODE ###

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

for i in range(1, n):
  if n%i == 0:
    num1 = i
    num2 = n/i
    ans.append(num1+num2-2)
    
print(int(min(ans)))

### FIXED CODE ###

n = int(input())
ans = n-1

for i in range(1, int(n**0.5)+1):
  if n%i == 0:
    num1 = i
    num2 = n/i
    ans = min(ans, num1+num2-2)
    
print(int(ans))
### BUGGY CODE ###

from itertools import *
n=range(50001);a=list(n);a[1]=0
for i in range(2,224):a[i*2::i]=[0]*len(a[i*2::i])
for x in iter(input,'0'):x=int(x);y=x//2+1;print(sum(a[x-d]>0 for d in a[:y]))


### FIXED CODE ###

import bisect,sys
from itertools import *
n=range(50001);a=list(n);a[1]=0
for i in range(2,224):a[i*2::i]=[0]*len(a[i*2::i])
p=list(compress(n,a))
for x in map(int,sys.stdin):
 if x:print(len([1 for d in p[:bisect.bisect(p,x//2)]if a[x-d]]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

args = input().split()
n = int(args[0])
m = int(args[1])
ok_list = [0] * 100000
ok_cnt = 0
ng_cnt = 0
args_results = [input().split() for i in range(m)]
for args_result in args_results:
    target = int(args_result[0])
    score = args_result[1]
    if target in ok_list:
        continue
    else:
        if score == 'AC':
            ok_list[ok_cnt] = target
            ok_cnt += 1
        else:
            ng_cnt += 1
print ok_cnt, ng_cnt

### FIXED CODE ###

import sys
input = sys.stdin.readline

args = input().split()
n = int(args[0])
m = int(args[1])
ok = [False] * n
ng = [0] * n
for _ in range(m):
    target, score = input().split()
    target = int(target) - 1
    if score == 'AC':
        ok[target] = True
    else:
        if not ok[target]:
            ng[target] += 1

ok_cnt = 0
ng_cnt = 0
for i in range(n):
    if ok[i]:
        ok_cnt += 1
        ng_cnt += ng[i]
print(ok_cnt, ng_cnt)
### BUGGY CODE ###

from collections import deque
import numpy as np

H, W = list(map(int, input().split()))
field = [[i=='#' for i in input()] for _ in range(H)]
count = 0

def bfs():
  global count
  q = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
  while True:
    nq = deque()
    while len(q) > 0:
      y, x = q.popleft()
      for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
          continue
        if field[ny][nx]:
          continue
        field[ny][nx] = True
        nq.append((ny, nx))
    if len(nq) > 0:
      q = nq
    else:
      break
    count += 1
      
bfs()
print(count)

### FIXED CODE ###

from collections import deque
import copy

def main():
  H, W = map(int, input().split())
  maps = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if maps[i][j]])
  count = 0
  while True:
    nq = deque()
    while q:
      x, y = q.popleft()
      if x > 0 and not maps[x-1][y]:
        maps[x-1][y] = True
        nq.append((x-1,y))
      if y > 0 and not maps[x][y-1]:
        maps[x][y-1] = True
        nq.append((x,y-1))
      if x < H-1 and not maps[x+1][y]:
        maps[x+1][y] = True
        nq.append((x+1,y))
      if y < W-1 and not maps[x][y+1]:
        maps[x][y+1] = True
        nq.append((x,y+1))
    if nq:
      q = copy.copy(nq)
    else:
        break
    count += 1
  print(count)

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

sn,bn=map(int,input().split(" "))
fubensa=[int(sn*(sn-1)/2)]
if bn>1:
    br=[]
    for _ in range(bn):
        br.append(list(map(int, input().split(" "))))
    br=br[::-1]
    sg=[0 for n in range(sn+1)]
    sg[br[0][0]]=1
    sg[br[0][1]]=1
    gn=1
    fubensa.append(fubensa[0]-1)
    for bri in range(1,bn-1):
        si1=br[bri][0]
        si2=br[bri][1]
        sg1=sg[si1]
        sg2=sg[si2]
        if sg1+sg2==0:
            gn+=1
            sg[si1],sg[si2]=gn,gn
            fubensa.append(fubensa[bri]-1)
        elif sg1==0:
            fubensa.append(fubensa[bri] - sg.count(sg2))
            sg[si1]=sg2
        elif sg2==0:
            fubensa.append(fubensa[bri] - sg.count(sg1))
            sg[si2]=sg1
        elif sg1!=sg2:
            fubensa.append(fubensa[bri] - sg.count(sg1)*sg.count(sg2))
            sg=[sg1 if x==sg2 else x for x in sg]
        else:
            fubensa.append(fubensa[bri])
for x in fubensa[::-1]:
    print(x)

### FIXED CODE ###

sn,bn=map(int,input().split(" "))
fu=[int(sn*(sn-1)/2)]
gr_si=[n for n in range(sn+1)]
siL_gr=[[n] for n in range(sn+1)]
siL_br=[]
for _ in range(bn):
    siL_br.append(list(map(int, input().split(" "))))
siL_br=siL_br[::-1]

for bri in range(bn-1):
    si1,si2=siL_br[bri]
    gr1 = gr_si[si1]
    gr2 = gr_si[si2]
    if gr1==gr2:
        fu.append(fu[bri])
    else:
        lengr1 = len(siL_gr[gr1])
        lengr2 = len(siL_gr[gr2])
        if lengr1<lengr2:
            gr1,gr2=gr2,gr1
        fu.append(fu[bri]-lengr1*lengr2)
        for si in siL_gr[gr2]:
            gr_si[si]=gr1
        siL_gr[gr1]+=siL_gr[gr2]
        siL_gr[gr2]=[]

print(*fu[::-1],sep="\n")