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

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, A: "List[int]"):
    from collections import Counter
    import math
    from functools import lru_cache

    @lru_cache(None)
    def combination(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
    c = Counter(A)

    dp = [-1] * (N+1)
    ans = []
    for i in range(N):
        if dp[A[i]] != -1:
            ans.append(dp[A[i]])
        else:
            t = 0
            for k,v in c.items():
                if k == A[i]:
                    if v-1 >= 2:
                        t += combination(v-1, 2)
                else:
                    if v >= 2:
                        t += combination(v, 2)
            ans.append(t)
            dp[A[i]] = t
 
    for i in ans:
        print(i)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, A: "List[int]"):
    from collections import Counter
    import math
    from functools import lru_cache

    @lru_cache(None)
    def combination(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
    c = Counter(A)
    
    ta = 0
    for k,v in c.items():
        if v >= 2:
            ta += combination(v, 2)
            
    # dp = [-1] * (N+1)
    ans = []
    for i in range(N):
        t = ta
        if c[A[i]] >= 2:
            t -= combination(c[A[i]], 2)
        if c[A[i]]-1 >= 2:
            t += combination(c[A[i]]-1, 2)
        
        ans.append(t)

 
    for i in ans:
        print(i)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

r1,c1,r2,c2=map(int,input().split())
MOD=10**9+7

from scipy.special import comb

def comb_mod(n,k):
  return comb(n,k,exact=True)%MOD

ans=comb_mod(r2+c2+2,r2+1)+comb_mod(r1+c1,r1)-comb_mod(c1+r2+1,c1)-comb_mod(c2+r1+1,r1)
ans%=MOD
print(ans)


### FIXED CODE ###

r1,c1,r2,c2=map(int,input().split())

mod = 10**9+7
MAX_N = 3*10**6

fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1] = pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
    fact_inv[i] = fact_inv[i+1]*(i+1)%mod

def comb(n,k,mod):
    if n<k:return 0
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

ans=0
ans+=comb(c1+r1,r1,mod)
ans%=mod
ans-=comb(c1+r2+1,r2+1,mod)
ans%=mod
ans-=comb(c2+r1+1,r1,mod)
ans%=mod
ans+=comb(c2+r2+2,r2+1,mod)
ans%=mod

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

import sys
from collections import deque
sys.setrecursionlimit(10**9)
N = int(input())
es = [[] for i in range(N*(N-1)//2)]
se = [[] for i in range(N*(N-1)//2)]
ins = [0]*(N*(N-1)//2)
dp = [-1]*(N*(N-1)//2)
ID = [[0]*N for i in range(N)]
count = 0
for i in range(N):
  for j in range(N):
    if i<j:
      ID[i][j] = count
      count += 1
def TP_sort(E, ins, start):
  q = deque(start)
  res = []
  while q:
    p = q.popleft()
    res += [p]
    for c in E[p]:
      ins[c] -= 1
      if ins[c]==0:
        q.append(c)
  for i in ins:
    if i>0:
      return -1
  return res

def dfs(e):
  if dp[e]!=-1:
    return dp[e]
  m = 0
  for ex in se[e]:
    x = dfs(ex)
    if x>m:
      m = x
  dp[e] = m+1
  return m+1

for i in range(N):
  inf = [int(i)-1 for i in input().split()]
  for j in range(N-2):
    x = min(i, inf[j])
    y = max(i, inf[j])
    nx = min(i, inf[j+1])
    ny = max(i, inf[j+1])
    t = ID[x][y]
    nt = ID[nx][ny]
    es[t] += [nt]
    se[nt] += [t]
    ins[nt] += 1
start = [v1 for v1 in range(len(ins)) if ins[v1]==0]
ls = TP_sort(es, ins, start)
if ls==-1:
  print(-1)
else:
  for i in start:
    dp[i] = 0
  print(dfs(ls[-1])+1)

### FIXED CODE ###

N = int(input())
es = [[] for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if es[j]==[]:
    return
  if es[j][-1]==i:
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 0
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    x = es[i].pop()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)
### BUGGY CODE ###

N=int(input())
E=[[] for _ in range(N)]
for _ in range(N-1):
    A,B=map(int,input().split())
    E[A-1].append(B-1)
    E[B-1].append(A-1)
MOD=10**9+7

#dp=子ノードの数+1(自分)
dp=[1]*N

root=0
parent=[0]*N
order=[]
def dfs():
    parent[root]=root
    stack=[root]
    while stack:
        node=stack.pop()
        order.append(node)
        for ss in E[node]:
            if parent[node]!=ss:
                stack.append(ss)
                parent[ss]=node

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow(pow(2,N-1,MOD),MOD-2,MOD)
    for i in reversed(order):
        if root!=i:
            dp[parent[i]]+=dp[i]
        p=0
        if len(E[i])>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in E[i]:
                size=0
                if parent[i]!=s:
                    size=dp[s]
                elif i!=root:
                    size=N-dp[i]
                else:
                    continue
                p1+=(1<<size)-1
                p1%=MOD
            p=1-(p0*p1)
            p%=MOD
        ans+=p
        ans%=MOD
    #頂点iが白の確率
    ans=ans*inv2%MOD
    print(ans)

dfs()
solve()


### FIXED CODE ###

N=int(input())
E=[[] for _ in range(N)]
for _ in range(N-1):
    A,B=map(int,input().split())
    E[A-1].append(B-1)
    E[B-1].append(A-1)
MOD=10**9+7

#dp=子ノードの数+1(自分)
dp=[1]*N

root=0
parent=[0]*N
order=[]
def dfs():
    parent[root]=root
    stack=[root]
    while stack:
        node=stack.pop()
        order.append(node)
        for ss in E[node]:
            if parent[node]!=ss:
                stack.append(ss)
                parent[ss]=node

pow2=[1]*(N+1)
for i in range(1,len(pow2)):
    pow2[i]=pow2[i-1]*2%MOD

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow(pow2[N-1],MOD-2,MOD)
    for i in reversed(order):
        if root!=i:
            dp[parent[i]]+=dp[i]
        p=0
        if len(E[i])>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in E[i]:
                size=0
                if parent[i]!=s:
                    size=dp[s]
                elif i!=root:
                    size=N-dp[i]
                else:
                    continue
                p1+=pow2[size]-1
            p=1-(p0*p1)
            p%=MOD
        ans+=p
        ans%=MOD
    #頂点iが白の確率
    ans=ans*inv2%MOD
    print(ans)

dfs()
solve()
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict
import math
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def IIR(n): return [II() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
mod = 1000000007

#A
"""
n,a,b = LI()
ans = [min(a,b),max(0,a+b-n)]
print(ans[0],ans[1])
"""

#B
"""
n = II()
a = S()
b = S()
c = S()
ans = 0
for i in range(n):
    if a[i] == b[i]:
        if b[i] == c[i]:
            continue
        else:
            ans += 1
    else:
        if b[i] == c[i] or c[i] == a[i]:
            ans += 1
        else:
            ans += 2
print(ans)
"""

#C
"""
n = II()
c = LIR(n)
c.sort(key = lambda x:-x[0]-x[1])
ans = 0
i = 0
for i in range(n):
    x,y = c.pop(0)
    if i%2 == 0:
        ans += x
    else:
        ans -= y
print(ans)
"""

#D
n,m = LI()
c = LIR(n-1+m)
for i in range(n-1+m):
    c[i][0] -= 1
    c[i][1] -= 1
l = []
v = [[] for i in range(n)]
ins = [0 for i in range(n)]
d = [[] for i in range(n)]
for a,b in c:
    v[a].append(b)
    ins[b] += 1
ans = [-1 for i in range(n)]
q = []
for i in range(n):
    if ins[i] == 0:
        q.append(i)
i = -1
lis = [True for i in range(n)]
while q:
    i = q.pop(0)
    for j in v[i]:
        ans[j] = i
        ins[j] -= 1
        if ins[j] == 0:
            q.append(j)
for i in ans:
    print(i+1)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
import math
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def IIR(n): return [II() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
mod = 1000000007

#A
"""
n,a,b = LI()
ans = [min(a,b),max(0,a+b-n)]
print(ans[0],ans[1])
"""

#B
"""
n = II()
a = S()
b = S()
c = S()
ans = 0
for i in range(n):
    if a[i] == b[i]:
        if b[i] == c[i]:
            continue
        else:
            ans += 1
    else:
        if b[i] == c[i] or c[i] == a[i]:
            ans += 1
        else:
            ans += 2
print(ans)
"""

#C
"""
n = II()
c = LIR(n)
c.sort(key = lambda x:-x[0]-x[1])
ans = 0
i = 0
for i in range(n):
    x,y = c.pop(0)
    if i%2 == 0:
        ans += x
    else:
        ans -= y
print(ans)
"""

#D
import queue
n,m = LI()
c = LIR(n-1+m)
for i in range(n-1+m):
    c[i][0] -= 1
    c[i][1] -= 1
v = [[] for i in range(n)]
ins = [0 for i in range(n)]
for a,b in c:
    v[a].append(b)
    ins[b] += 1
ans = [-1 for i in range(n)]
q = queue.Queue()
for i in range(n):
    if ins[i] == 0:
        q.put(i)
while not q.empty():
    i = q.get()
    for j in v[i]:
        ans[j] = i
        ins[j] -= 1
        if ins[j] == 0:
            q.put(j)
for i in ans:
    print(i+1)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T
### BUGGY CODE ###

import copy
import fractions
from functools import reduce
N=int(input())
A=list(map(int,input().split()))
l=[]
for i in A:
    if len(A)>=3:
        B=copy.deepcopy(A)
        B.remove(i)
        l.append(reduce(fractions.gcd,B))
    else:
        l.append(i)
print(max(l))

### FIXED CODE ###

from  fractions import gcd
N=int(input())
A=list(map(int,input().split()))
L=[0]
R=[0]
ans=1
for i in range(N-1):
    R.append(gcd(R[-1], A[-1-i]))
    L.append(gcd(L[-1], A[i]))
print(max(gcd(l,r)for l,r in zip(L,R[::-1])))
### BUGGY CODE ###

from heapq import heapify,heappop,heappush
import sys
read=sys.stdin.readline
class mset:
    def __init__(self):
        self.p,self.q,self.dic=[],[],{}
        heapify(self.p);heapify(self.q)
    def add(self,a):
        heappush(self.p,a)
        if not a in self.dic:
            self.dic[a]=1
        else:
            self.dic[a]+=1
    def delete(self,a):
        if a in self.dic and self.dic[a]>0:
            heappush(self.q,a)
            self.dic[a]-=1
    def search(self,a):
        return a in self.dic
    def minimum(self):
        while self.q and self.p[0]==self.q[0]:
            heappop(self.p);heappop(self.q)
        return self.p[0] if self.p else None

N,Q=map(int,read().split())
event=[]
for i in range(N):
    S,T,X=map(int,read().split())
    event.append((1,S-X,X))
    event.append((0,T-X,X))
event.sort(key=lambda x:x[1])

s=mset()
now=0
for i in range(Q):
    D=int(read())
    while(now<len(event) and event[now][1]<=D):
        if event[now][0]==1:
            s.add(event[now][2])
        elif event[now][0]==0:
            s.delete(event[now][2])
        now+=1
    m=s.minimum()
    print(-1 if m==None else m)

### FIXED CODE ###

from heapq import heapify,heappop,heappush
import sys
read=sys.stdin.readline
class mset:
    def __init__(self):
        self.p,self.q=[],[]
        heapify(self.p);heapify(self.q)
    def add(self,a):
        heappush(self.p,a)
    def delete(self,a):
            heappush(self.q,a)
    def minimum(self):
        while self.q and self.p[0]==self.q[0]:
            heappop(self.p);heappop(self.q)
        return self.p[0] if self.p else None

N,Q=map(int,read().split())
event=[]
for i in range(N):
    S,T,X=map(int,read().split())
    event.append((1,S-X,X))
    event.append((0,T-X,X))

s=mset()
now=0
for i in range(Q):
    D=int(read())
    event.append((2,D,0))
event.sort(key=lambda x:(x[1],x[0]))

for c,t,w in event:
    if c==0:
        s.delete(w)
    elif c==1:
        s.add(w)
    else:
        m=s.minimum()
        print(-1 if m==None else m)
### BUGGY CODE ###

K = int(input())

import itertools
import math
from functools import reduce

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

lis = [i for i in range(1,K+1)]
s = 0
for team in itertools.product(lis, repeat = 3):
    s += gcd_list(team)
print(s)




### FIXED CODE ###

K = int(input())

import itertools
import math
from functools import reduce

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

lis = list(range(1,K+1))
S = [gcd_list(team) for team in itertools.product(lis, repeat = 3)]

print(sum(S))
### BUGGY CODE ###

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

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

mat = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    mat[a][b] += 1


def solve():

    for i in range(N+1):
        for j in range(1, N+1):
            mat[i][j] += mat[i][j-1]

    ans = []

    for _ in range(Q):
        ql, qr = map(int, input().split())
        tmp = 0
        for i in range(ql, qr+1):
            tmp += mat[i][qr] - mat[i][ql-1]
        ans.append(tmp)

    for a in ans:
        print(a)


def solve2():

    for i in range(1, N+1):
        for j in range(1, N+1):
            mat[i][j] += mat[i-1][j] + \
                mat[i][j-1] - mat[i-1][j-1]

    ans = [0]*Q
    for i in range(Q):
        ql, qr = map(int, input().split())
        t = mat[qr][qr] - mat[ql-1][qr] - mat[qr][ql-1] + mat[ql-1][ql-1]
        ans[i] = t

    for a in ans:
        print(a)


solve()


### FIXED CODE ###

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

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

mat = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    mat[a][b] += 1


def solve():

    for i in range(N+1):
        for j in range(1, N+1):
            mat[i][j] += mat[i][j-1]

    ans = []

    for _ in range(Q):
        ql, qr = map(int, input().split())
        tmp = 0
        for i in range(ql, qr+1):
            tmp += mat[i][qr] - mat[i][ql-1]
        ans.append(tmp)

    for a in ans:
        print(a)


def solve2():

    for i in range(1, N+1):
        for j in range(1, N+1):
            mat[i][j] += mat[i-1][j] + \
                mat[i][j-1] - mat[i-1][j-1]

    ans = [0]*Q
    for i in range(Q):
        ql, qr = map(int, input().split())
        t = mat[qr][qr] - mat[ql-1][qr] - mat[qr][ql-1] + mat[ql-1][ql-1]
        ans[i] = t

    for a in ans:
        print(a)


solve2()
### BUGGY CODE ###

n =int(input())

ans =[]
for i in range(1,n+1):
  if (i ** 0.5).is_integer() and i <= n:
    ans.append(i)
    
ans.sort()    
print(ans[-1])
    
    

    


### FIXED CODE ###

n = int(input())
m = 1
for i in range(1, n):
    if i ** 2 > n:
        break
    m = i ** 2
print(m)
### BUGGY CODE ###

N=int(input())
S=list(range(1, N+1))#頂点の数
H = [list(map(int,input().split())) for i in range(N-1)]#辺のリスト
F = 0
tyouten = int(N*(N+1)*(N+2)/6)
for i in range(1,N+1):
    for j in range(i,N+1):	
        Hselect = [H[x] for x in range(N-1) if i <= H[x][0] <= j and i <= H[x][1] <= j]#L以上R以下の頂点で構成される辺のリスト
        F += len(Hselect)
#以上の処理をL＝1〜N、R＝L〜Nまで繰り返す
print(tyouten-F)#頂点数からHselectの要素数を引いた数＝連結成分数

### FIXED CODE ###

N=int(input())
S=list(range(1, N+1))#頂点の数
H = [sorted(list(map(int,input().split()))) for i in range(N-1)]#辺のリスト。頂点は右にいくほど大きい
F = 0
tyouten = int(N*(N+1)*(N+2)/6)
for i in range(len(H)):
    F += H[i][0]*(N-H[i][1]+1)#uVの組み合わせによって得られる辺の数をFに追加
print(tyouten-F)#頂点数からHselectの要素数を引いた数＝連結成分数
### BUGGY CODE ###


if __name__ == '__main__':
    d = input()
    n = int(input())
    for _ in range(n):
        q = input()
        if q == '': break
        elif q.startswith('1'):
            d = d[::-1]
        elif q.startswith("2 1"):
            d = q[-1]+d
        elif q.startswith("2 2"):
            d=d+q[-1]
    print(d)

### FIXED CODE ###

if __name__ == '__main__':
    d = input()
    n = int(input())
    qs = [input() for e in range(n)]
    s = []
    e = []
    r = False
    for q in qs:
        if q == '1':
            r = not(r)
        elif q.startswith("2 1"):
            e.append(q[-1]) if r else s.append(q[-1])
        else:
            s.append(q[-1]) if r else e.append(q[-1])
    print("".join(e[::-1]) + d[::-1] + "".join(s) if r else "".join(s[::-1]) + d + "".join(e))
### BUGGY CODE ###

N, Q = map(int, input().split())
 
AB = []
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    AB.append((a, b))
    graph[a].append(b)
    graph[b].append(a)
AB = sorted(AB, key=lambda x: (x[1], x[0]))
 
root = 0
q = [root]
parent = [-1] * N
while q:
    x = q.pop(0)
    p = parent[x]
    for y in graph[x]:
        if y == p:
            continue
        parent[y] = x
        q.append(y)

C = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    p = p - 1
    C[p] = C[p] + x

for a, b in AB:
    if a != parent[b]:
        tmp = a
        a = b
        b = tmp
    C[b] = C[b] + C[a]

print(*C)

### FIXED CODE ###

from queue import deque


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

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

C = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    C[p - 1] += x

P = [-1] * N

root = 0
q = deque([root])
while q:
    x = q.popleft()
    for y in graph[x]:
        if y == P[x]:
            continue
        C[y] += C[x]
        q.append(y)
        P[y] = x

print(*C)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

N,mod=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1)]

#N=10**5
#mod=10**8
#import random
#EDGE=[[i,random.randint(1,i-1)] for i in range(2,N+1)]

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

for x,y in EDGE:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

QUE=deque()
DPDICT=dict()

for i in range(1,N+1):
    if len(EDGELIST[i])==1:
        #DPDICT[(i,EDGELIST[i][0])]=2
        QUE.append(i)


def SCORE(point):
    ANS=1
    for to in EDGELIST[point]:
        ANS=ANS*DPDICT[(to,point)]%mod
    return ANS

def dp(x,y):
    if DPDICT.get((x,y))!=None:
        return DPDICT[(x,y)]

    ANS=1
    for to in EDGELIST[x]:
        if to==y:
            continue
        ANS=ANS*dp(to,x)%mod

    DPDICT[(x,y)]=ANS+1
    return ANS+1

while QUE:
    x=QUE.pop()
    for to in EDGELIST[x]:
        if DPDICT.get((x,to))==None:
            dp(x,to)
            QUE.append(to)


for i in range(1,N+1):
    print(SCORE(i))


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

N,mod=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1)]

if N==1:
    print(1)
    sys.exit()

EDGELIST=[[] for i in range(N+1)]
for x,y in EDGE:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

SCORELIST=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
PRODLIST=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
PRODLIST_rev=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
EDICT=dict()

for i in range(1,N+1):
    for j in range(len(EDGELIST[i])):
        EDICT[(i,EDGELIST[i][j])]=j

def dp(x,y):
    if SCORELIST[y][EDICT[(y,x)]]!=-1:
        return SCORELIST[y][EDICT[(y,x)]]

    ANS=1
    for to in EDGELIST[x]:
        if to==y:
            continue
        ANS=ANS*dp(to,x)%mod

    SCORELIST[y][EDICT[(y,x)]]=ANS+1   
    return ANS+1

def dp2(x,y):
    if PRODLIST[x][0]==-1:
        PRODLIST[x][0]=(SCORELIST[x][0])%mod
        for i in range(1,len(EDGELIST[x])):
            PRODLIST[x][i]=PRODLIST[x][i-1]*SCORELIST[x][i]%mod

        PRODLIST_rev[x][-1]=SCORELIST[x][-1]
        for i in range(len(EDGELIST[x])-2,-1,-1):
            PRODLIST_rev[x][i]=PRODLIST_rev[x][i+1]*SCORELIST[x][i]%mod

    if len(EDGELIST[x])==1:
        ANS=1
    elif EDICT[(x,y)]==0:
        ANS=PRODLIST_rev[x][1]
    elif EDICT[(x,y)]==len(EDGELIST[x])-1:
        ANS=PRODLIST[x][EDICT[(x,y)]-1]
    else:
        ANS=PRODLIST[x][EDICT[(x,y)]-1]*PRODLIST_rev[x][EDICT[(x,y)]+1]%mod

    SCORELIST[y][EDICT[(y,x)]]=ANS+1

for to in EDGELIST[1]:
    dp(to,1)

QUE=deque([1])
check=[0]*(N+1)

while QUE:
    x=QUE.pop()
    if check[x]==1:
        continue
    for to in EDGELIST[x]:
        if check[x]==0 or check[to]==0:
            dp2(x,to)
            QUE.append(to)
    check[x]=1

for i in range(1,N+1):
    print(PRODLIST[i][-1])
### BUGGY CODE ###

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

AB = []

for _ in range(M):
    A_i, B_i = map(int, input().split())
    AB.append([A_i, B_i])
    
can_move = {}

MAX_COMBINATION = N * (N-1) // (2 * 1)
ans = [MAX_COMBINATION]
#print(AB)
for i in range(1, N+1):
    can_move[i] = set([i])


#print(can_move)
#print("-----")
for bridge in reversed(AB):
    merge_island = can_move[bridge[0]] | can_move[bridge[1]] 
    import copy
    tmp = copy.deepcopy(can_move[bridge[0]])
    for island in tmp:
        can_move[island] = merge_island
    tmp = copy.deepcopy(can_move[bridge[1]])
    for island in tmp:
        can_move[island] = merge_island
    
    
    #print(bridge)
    #print(can_move)
    
    can_move_count = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if j in can_move[i]:
                can_move_count += 1
    #print(can_move_count)
    ans.append(MAX_COMBINATION - can_move_count)



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

### FIXED CODE ###

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

AB = []

for _ in range(M):
    A_i, B_i = map(int, input().split())
    AB.append([A_i, B_i])

class UnionFind():
    def __init__(self, n):
        self.parent = [-1 for _ in range(n)] # 親なら -1 * サイズ
        
    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
    def size(self, x):
        x = self.root(x)
        return -1 * self.parent[x]
    
    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        x_size = self.size(x)
        y_size = self.size(y)
        if x_size < y_size:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        return True
        
max_inconvenience = N * (N - 1) // 2 
ans = [max_inconvenience]
uf = UnionFind(N)
for bridge in reversed(AB):
    x = uf.root(bridge[0] - 1)
    y = uf.root(bridge[1] - 1)

    if x != y:
        x_size = uf.size(x)
        y_size = uf.size(y)
        ans_tmp = max_inconvenience - x_size * y_size
        max_inconvenience = ans_tmp
        uf.union(x, y)
    else:
        ans_tmp = max_inconvenience
    ans.append(ans_tmp)
    
for a in reversed(ans[:-1]):
    print(a)