Harryxun/stf_run huggingface dataset:
N = int(input())
lines = [[] for _ in range(N)]
for _ in range(N-1):
  i,j,w = map(int,input().split())
  lines[i-1].append((j-1,w))
  lines[j-1].append((i-1,w))

ans = [-1]*N 
def dfs(s, c):
  if ans[s] != -1:
    return
  else:
    ans[s] = c
    for t,w in lines[s]:
      if w%2==0:
        dfs(t,c)
      else:
        dfs(t,c^1)
      
dfs(0, 0)

print('\n'.join(map(str,ans)))




### FIXED CODE ###

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N = int(input())

lines = defaultdict(set)
for i in range(N-1):
    u,v,w = inpl()
    u,v = u-1,v-1
    lines[u].add((v,w))
    lines[v].add((u,w))

ans = [0]*N

def dfs(s,c):
    global ans
    for t,d in list(lines[s]):
        if ans[t] == 0:
            if d%2 == 0:
                ans[t] = c
                dfs(t,c)
            else:
                ans[t] = -c
                dfs(t,-c)


dfs(0,1)
for a in ans:
    if a == -1:
        print(0)
    else:
        print(1)
import numpy as np

l = map(int, raw_input().split())
if l[0]==l[1]:
	print(l[2])
elif l[0] ==l[2]:
	print(l[1])
elif l[1] ==l[2]:
	print(l[0])

### FIXED CODE ###

l = list(map(int, input().split()))
if l[0]==l[1]:
	print(l[2])
elif l[0] ==l[2]:
	print(l[1])
elif l[1] ==l[2]:
	print(l[0])
n, r = map(int, input().split())
if r-n >= 2019:
  print(0)
  sys.exit(0)
mini = 2019
#nM = n % 2019
#rM = r % 2019
for i in range(n, r+1):
  for j in range(i+1, r+1):
    mini = min((i*j)%2019, mini)
print(mini)

### FIXED CODE ###

n, a, b = map(int, input().split())

if n * a < b:
  print(n * a)
else:
  print(b)
import sys
sys.setrecursionlimit(10000)

n, m = map(int, input().split())
abc = [tuple(int(x) - 1 for x in input().split()) for _ in range(m)]

#res = [[9999999 for _ in range(n)] for _ in range(n)]

e = [dict() for _ in range(n)]

for i in range(m):
    a, b, c = abc[i][0], abc[i][1], abc[i][2]
    e[a][b] = [c, i]
    e[b][a] = [c, i]

ans = set()

for i in range(n-1):
    for j in range(i + 1, n):
        temp = [[0, i]]
        res = []
        for k in range(n):
            next = []
            for x in temp:
                if x[1] == j:
                    res.append(x)
                    continue
                for z in e[x[1]].keys():
                    if len(x) == 2:
                        next.append([ x[0] + e[x[1]][z][0], z ] + [ e[x[1]][z][1] ])
                    else:
                        next.append([ x[0] + e[x[1]][z][0], z ] + x[2:] + [ e[x[1]][z][1] ])
            temp = [] + next
        mr = 99999999
        p = 0
        for i in range(len(res)):
            if res[i][0] < mr:
                mr = res[i][0]
                p = i
        #print(set(res[p][2:]))
        ans = ans | set(res[p][2:])

print(m - len(ans))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
abc = [tuple(int(x) - 1 for x in input().split()) for _ in range(m)]

dist = [[9999999 for _ in range(n)] for _ in range(n)]

e = [dict() for _ in range(n)]

for i in range(m):
    a, b, c = abc[i][0], abc[i][1], abc[i][2]
    e[a][b] = c + 1
    e[b][a] = c + 1

for i in range(n):
    h = []
    heapq.heappush(h, [0, i])
    temp = set()
    #temp.add(i)
    while len(temp) < n:
        d, p = heapq.heappop(h)
        while p in temp:
            d, p = heapq.heappop(h)
        dist[i][p] = d
        temp.add(p)
        for x in e[p].keys():
            heapq.heappush(h, [d + e[p][x], x])

#for i in range(n): print(dist[i])

ans = m
for a, b, c in abc:
    for i in range(n):
        if c + 1 == dist[a][i] - dist[b][i]:
            ans -= 1
            break
print(ans)
import itertools as it

n,m=map(int,input().split())
ans=[]
for i in range(n):
    a,b=map(int,input().split())
    ans.append([a,b])
    ans.append([b,a])
  
count,a=0,0
for e in it.permutations(range(n)):
    if e[0]!=0:
        break
    
    for i in range(len(e)-1):
        if [e[i]+1,e[i+1]+1] in ans:
            count=1
        else:
            count=0
            
    a+=count
    
print(a)
        

### FIXED CODE ###

import itertools as it
import sys

N, M = map(int, input().split())
if N==0 or M==0:
    print(0)
    sys.exit()
a=[]

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

ans=0
for e in it.permutations(range(N)):
    if e[0]!=0:
        break
        
    count=1
    for j in range(N-1):
        if [e[j]+1,e[j+1]+1] in a:
            count*=1
        else:
            count*=0
            break
            
    ans+=count

print(ans)
n = int(input())
if n ==1 :
  print("Hello World")
else :
  a = [input() for i in range(2)]
  print(a[o]+ a[1])

### FIXED CODE ###

n = int(input())
if n ==1 :
  print("Hello World")
else :
  a = [int(input()) for i in range(n)]
  print(a[0] + a[1])
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n = ni()
    p = na()

    cnt=0
    for i in range(1, n+1):
        if p[i - 1] == i:
            p[i - 1], p[i] = p[i], p[i - 1]
            cnt+=1
    print(cnt)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n = ni()
    p = na()

    cnt = 0
    for i in range(1, n + 1):
        if i<n:
            if p[i - 1] == i:
                p[i - 1], p[i] = p[i], p[i - 1]
                cnt += 1
        else:
            if p[i - 1] == i:
                p[i - 1], p[i-2] = p[i-1], p[i - 2]
                cnt += 1
    print(cnt)


if __name__ == '__main__':
    main()
a=int(input())
b=input().split(" ")
f=[]
if a>=3:
    for p in range (0,a-2):
        if int(b[p])-int(b[p+1])>1:
            f.append("miss")
        elif int(b[p])-int(b[p+1])==1:
            if int(b[p+1])-int(b[p+2])==1:
                f.append("miss")
    if int(b[a-2])-int(b[a-1])>1:
        f.append("miss")
elif a=3:
    if int(b[0])-int(b[1])>1:
        f.append("miss")
    elif int(b[1])-int(b[2])>1:
        f.append("miss")
    elif int(b[0])-int(b[2])>1:
        f.append("miss")
elif a=2:
    if int(b[0])-int(b[1])>1:
        f.append("miss")

if "miss" not in f:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a=input().split(" ")
A=int(a[0])
B=int(a[1])
C=int(a[2])
if C-A+B>=0:
    print(C-A+B)
else:
    print(0)
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[list(S()) for _ in range(h)]

  q=collections.deque()
  nokori=h*w
  dist=[[-1]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        q.append((i,j))
        dist[i][j]=0
        nokori-=1

  while q:
    if nokori==0:
      return d

    y,x=q.popleft()

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny and ny<h and 0<=nx and nx<w:
        if field[ny][nx]=='.':
          field[ny][nx]='#'
          d=dist[y][x]+1
          dist[ny][nx]=d
          q.append((ny,nx))
          nokori-=1

  return d

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[list(S()) for _ in range(h)]
  d=0

  q=collections.deque()
  nokori=h*w
  dist=[[-1]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        q.append((i,j))
        dist[i][j]=0
        nokori-=1

  while q:
    if nokori==0:
      return d

    y,x=q.popleft()

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny and ny<h and 0<=nx and nx<w:
        if field[ny][nx]=='.':
          field[ny][nx]='#'
          d=dist[y][x]+1
          dist[ny][nx]=d
          q.append((ny,nx))
          nokori-=1

  return d

# main()
print(main())
def main():
    N = input()
    A = list(map(int,input().split()))

    if 0 in A:
        print(0)
        return

prod = 1
for a in A:
    prod *= a
    if prod > 1000000000000000000:
        print(-1)
        return

print(prod)

main()


### FIXED CODE ###

N = input()
A = list(map(int,input().split()))
def main(A):
    if 0 in A:
        print(0)
        return

    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return

    print(prod)

main(A)
import sys
for line in sys.stdin:
    a,b = line.split()
    a,b = int(a),int(b)
    print '%d %d %5.8f' %(a/b, a%b, 1.0*a/b)

### FIXED CODE ###

a, b = map(int, raw_input().split())
print '%d %d %.12f' %(a/b, a%b, 1.0*a/b)
from math import factorial
L = [0]
N = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in range(N):
    L.append(L[-1] + A[i])
ind = list(set(L))
for i in ind:
    n = L.count(i)
    if n > 1:
        cnt += factorial(n) / factorial(2) / factorial(n - 2)
print(int(cnt))

### FIXED CODE ###

from math import factorial as f
L = [0]
N = int(input())
A = list(map(int, input().split()))
cnt = 0
dic = {}
dic[0] = 1
for i in range(N):
    n = L[-1] + A[i]
    L.append(n)
    dic.setdefault(n, 0)
    dic[n] += 1
for key in dic.keys():
    if dic[key] > 1:
        cnt += f(dic[key]) // f(2) // f(dic[key] - 2)
print(int(cnt))
n,k=int(input().split())
h=list(map(int,input().split()))
result=0
for i in range(n):
  if h[i]>=k:
    result+=1
print(result)


### FIXED CODE ###

s,t=(int(x) for x in input().split())
n=list(map(int,input().split()))
k=0
for i in range(s):
    if t<=n[i]:
        k+=1
print(k)
import math

N = int(input())
ratios = []
for i in range(N):
    t, a = map(int, input().split())
    ratios.append([t, a])

def min_vote(index):
    if index == N-1:
        return ratios[N-1-index]

    mt, ma = min_vote(index+1)
    t, a = ratios[N-1-index]
    min_ratio = max(math.ceil(mt / t), math.ceil(ma / a))
    return [t * min_ratio, a * min_ratio]

print(sum(min_vote(0)))

### FIXED CODE ###

import math

N = int(input())
pt = 1
pa = 1
for i in range(N):
    t, a = map(int, input().split())

    t_ratio = pt // t
    a_ratio = pa // a
    if pt % t != 0:
        t_ratio += 1
    if pa % a != 0:
        a_ratio += 1
    min_ratio = max(t_ratio, a_ratio)
    pt = t * min_ratio
    pa = a * min_ratio

print(pt+pa)
N,K = list(map(int,input().split()))

tree = [[] for _ in range(N)]

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

ans = []
def wfs(now,back):
    if now != 0:
        cnt = K - 2 #まず一個上のを引く。
    else:
        cnt = K - 1
    for nxt in tree[now]:
        if nxt != back:
            ans.append(cnt)
            cnt = cnt - 1
            wfs(nxt,now)

ans.append(K)
wfs(0,-1)

ans2 = 1
for j in range(N):
    ans2 = (ans2 * ans[j]) % (10**9+7)
print(ans2)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
 

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

tree = [[] for _ in range(N+10)]

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

ans = []
def wfs(now,back):
    if now != 0:
        cnt = K - 2 #まず一個上のを引く。
    else:
        cnt = K - 1
    for nxt in tree[now]:
        if nxt != back:
            ans.append(cnt)
            cnt = cnt - 1
            wfs(nxt,now)

ans.append(K)
wfs(0,-1)

ans2 = 1
for j in range(len(ans)):
    ans2 = (ans2 * ans[j]) % (10**9+7)
print(ans2)
n, k = map(int, input().split())

if k <= (n - 1) * (n - 2) // 2:
    raise Exception
else:
    print(-1)


### FIXED CODE ###

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

if k <= (n - 1) * (n - 2) // 2:
    g = [0] * (n * n)
    for i in range(n * n):
        u = i // n
        v = i % n
        if u < v:
            g[i] = 1

    i = 0
    for _ in range(k):
        while g[i] == 0 or i % n == n - 1:
            i += 1
        g[i] = 0

    cnt = sum(g)
    print(cnt)
    for i, e in enumerate(g):
        if e:
            u = i // n + 1
            v = i % n + 1
            print(u, v)

else:
    print(-1)
N, K = list(map(int,input().split()))
move_list = list(map(int,input().split()))
 
  
test = 1
find_f = {}
for i in range(N):
  find_f[i+1]=[]
 
find_f[1].append(0)
for i in range(K):
  test = move_list[test-1]
  find_f[test].append(i+1)
  if len(find_f[test]) == 2 and find_f[test][1]-find_f[test][0]<=100000:
    state ,f = test, find_f[test]
    break
  
K = K-f[0]
f = f[1]-f[0]
remain = K%f
 
for i in range(remain):
  state = move_list[state-1]
  
print(state)
#state = 1

### FIXED CODE ###

N, K = list(map(int,input().split()))
move_list = list(map(int,input().split()))
 
  
test = 1
find_f = {}
for i in range(N):
  find_f[i+1]=[]
 
find_f[1].append(0)
for i in range(K):
  test = move_list[test-1]
  find_f[test].append(i+1)
  if len(find_f[test]) == 2 and find_f[test][1]-find_f[test][0]<=1000000:
    state ,f = test, find_f[test]
    break
try:
  K = K-f[0]
  f = f[1]-f[0]
  remain = K%f
  for i in range(remain):
    state = move_list[state-1]
 
  print(state)
except:
  print(test)
#state = 1
s = (input()
l = list(s)
flag = 0
for i in range(0,len(l)-1):
	if l[i+1]==l[i]:
    	flag=1
   		break
if flag==1:
	print('Bad')
else:
	print('Good')

### FIXED CODE ###

s = input()
l = list(s)
flag = 0
for i in range(0,len(l)-1):
	if l[i+1]==l[i]:
		flag=1
		break
if flag==1:
	print('Bad')
else:
	print('Good')
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)

nums = {}
nums[1] = 2
nums[2] = 5
nums[3] = 5
nums[4] = 4
nums[5] = 5
nums[6] = 6
nums[7] = 3
nums[8] = 7
nums[9] = 6

dp = [0]*(N+1)

for i in range(1, N+1):
    make = True
    for a in A:
        if i-nums[a] >= 0:
            dp[i] = max(1, dp[i-nums[a]]+1)
            make = False
    if make:
        dp[i] = -float('inf')

ans = ""
i = N
while i > 0:
    for a in A:
        if dp[i]-1 == dp[i-nums[a]]:
            ans += str(a)
            i = i-nums[a]
            break
print(ans)


### FIXED CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)

nums = {}
nums[1] = 2
nums[2] = 5
nums[3] = 5
nums[4] = 4
nums[5] = 5
nums[6] = 6
nums[7] = 3
nums[8] = 7
nums[9] = 6

dp = [-float('inf')]*(N+1)
dp[0] = 0

for i in range(N+1):
    for a in A:
        if i-nums[a] >= 0:
            dp[i] = max(dp[i], dp[i-nums[a]]+1)

ans = ""
i = N
while i > 0:
    for a in A:
        if i >= nums[a] and dp[i]-1 == dp[i-nums[a]]:
            ans += str(a)
            i = i-nums[a]
            break
print(ans)
import re
a,b=map(int,input().split())
s=input()
if re.fullmatch(^[0-9]{a}-[0-9]{b}$,s)==True:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

a,b=map(int,input().split())
s=input()
if s[a]=='-' and s.count('-')==1:
  print('Yes')
else:
  print('No')
A, B, C = map(int, input().split())

print(min( C - (A - B), 0)

### FIXED CODE ###

A, B, C = map(int, input().split())
print(max( C - (A - B), 0))
n,m=map(int,input().split())
print(min(s,c//2)+max(0,c-s*2)//4)

### FIXED CODE ###

s,c=map(int,input().split())
print(min(s,c//2)+max(0,c-s*2)//4)
import numpy as np
import math
n=int(input())
A=np.empty((n))
B=np.zeros((n))
count=0

for i in range(n):
    A[i]=input()


for i in range(n):
    if A[i]==1:
        B[i]=1
    elif A[i]==2:
        B[i]=0
    elif A[i]==3:
        B[i]=0
    elif A[i]==5:
        B[i]=0
    elif A[i]%2==0 :
        B[i]=1
    elif A[i]%3==0:
        B[i]=1
    elif A[i]%5==0:
        B[i]=1
    else:
        for j in range(2,int(math.sqrt(A[i]))):
            if A[i]%j==0:
                B[i]=1 
                break



for i in range(n):
    if B[i]==0:
        count=count+1

print(count)


### FIXED CODE ###

from math import sqrt

n=int(input())

count=0

for i in range(n):
    x=int(input())
    if x==1:
        count=count+1
    elif x!=2 and x%2==0:
        count=count+1
    elif x==2 or x==3 or x==5:
        count=count
    else:
        for j in range(2,int(sqrt(x))+1): 
            if x%j==0:
                count=count+1
                break


print(n-count)
n = int(input())
numbers = list(map(int, input().split()))

res = 0

for i in range(n):
  count = 0
  while True:
    if numbers[i]%2 == 1:
      break
    numbers[i] = numbers[i]/2 
    count += 1
  
  if count > res:
    res = count

print(res)

### FIXED CODE ###

s = input()
count = 0

for i in range(3):
  if s[i] == '1':
    count += 1
    
print(count)
import numpy as np

def iterate(mapdata, passed, curr, count):
    if curr == (passed.shape[0] - 1, passed.shape[1] - 1):
        return count

    if mapdata[curr[0]][curr[1]] == '#':
        return 100000 #passed[curr]
    
    #if passed[curr] < 100000:
    #    print(passed[curr], count)
    if passed[curr] <= count:
        return 100000
    passed[curr] = count
    
    ret = 100000
    if curr[0] < passed.shape[0] - 1:
        tmp = iterate(mapdata, passed, (curr[0] + 1, curr[1]), count + 1)
        ret = min(ret, tmp)
    if curr[1] < passed.shape[1] - 1:
        tmp = iterate(mapdata, passed, (curr[0], curr[1] + 1), count + 1)
        ret = min(ret, tmp)
    if curr[0] > 0:
        tmp = iterate(mapdata, passed, (curr[0] - 1, curr[1]), count + 1)
        ret = min(ret, tmp)
    if curr[1] > 0:
        tmp = iterate(mapdata, passed, (curr[0], curr[1] - 1), count + 1)
        ret = min(ret, tmp)

    return ret


h, w = map(int, input().split())
mapdata = [input() for y in range(h)]
dotsum = sum(mapdata[y].count('.') for y in range(h))

passed = np.zeros((h, w), np.int32)
passed[:, :] = 100000
count = iterate(mapdata, passed, (0, 0), 0)
#print(count)
print(dotsum - count - 1)

### FIXED CODE ###

import numpy as np

def iterate2(mapdata, passed, start):
    queue = [(start, 0)]

    while len(queue) > 0:
        curr, count = queue[0]
        del queue[0]
        if curr == (passed.shape[0] - 1, passed.shape[1] - 1):
            return count
        if mapdata[curr[0]][curr[1]] == '#':
            continue
        if passed[curr] > 0:
            continue
        passed[curr] = 1

        if curr[0] < passed.shape[0] - 1:
            queue.append(((curr[0] + 1, curr[1]), count + 1))
        if curr[1] < passed.shape[1] - 1:
            queue.append(((curr[0], curr[1] + 1), count + 1))
        if curr[0] > 0:
            queue.append(((curr[0] - 1, curr[1]), count + 1))
        if curr[1] > 0:
            queue.append(((curr[0], curr[1] - 1), count + 1))
    
    return -1

h, w = map(int, input().split())
mapdata = [input() for y in range(h)]
dotsum = sum(mapdata[y].count('.') for y in range(h))

passed = np.zeros((h, w), np.int8)
count = iterate2(mapdata, passed, (0, 0))
#print(dotsum)
#print(count)
if count > 0:
    print(dotsum - count - 1)
else:
    print(-1)
a,b,c = map(str,input().split)

s = set(["a","b","c"])

if len(s) == 2:
    print("Yes)
else:
    print("No")

### FIXED CODE ###

a,b,c = map(int,input().split())

s = set([a,b,c])

if len(s) == 2:
  print("Yes")
else:
  print("No")
class UnionFind:
    def __init__(self, length):
        self.par = [_ for _ in range(length)]
        self.size_dict  = dict([(i,1) for i in range(length)])

    def root(self,x):
        if (self.par[x] == x):
             return x
        else:
            #change connection 
            self.par[x] =self.root(self.par[x])
            return self.par[x]
    
    def unite(self,x,y):
        root_x = self.root(x)
        root_y = self.root(y)
        if (root_x==root_y):
            pass
        else:
            self.par[root_x] = root_y
            self.size_dict[root_y] += self.size_dict[root_x]
            self.size_dict[root_x] = -1
        
    def same(self,x,y):
        root_x = self.root(x)
        root_y = self.root(y)
        return root_x == root_y 
    
    def size(self,x):
        root_x = self.root(x)
        return self.size_dict[root_x]

"""
uf = UnionFind(5)
uf.unite(3,4)
uf.unite(1,2)
uf.unite(1,4)
print(uf.size_dict)
"""


N,M = [ int(i) for i in input().split(" ")]
edges = [ tuple([ int(num)-1 for num in  input().split(" ")]) for _ in range(M) ]
score= N*(N-1)/2
outputs = [score]
uf = UnionFind(N)
for edge in edges[:0:-1]:
    if not uf.same(*edge):
        score -= uf.size(edge[0]) * uf.size(edge[1])
        uf.unite(*edge)
    outputs.append(score)

for i in outputs[::-1]:
    print(int(i))


### FIXED CODE ###

class UnionFind:
    def __init__(self, length):
        self.par = [-1 for _ in range(length)]
        self.rank = [0 for _ in range(length)]
 
    def root(self,x):
        if (self.par[x] < 0 ):
             return x
        else:
            #change connection
            root = self.root(self.par[x])
            self.par[x] = root
            return root
    
    def unite(self,x,y):
        root_x = self.root(x)
        root_y = self.root(y)
        if (root_x==root_y):
            return 
        else:
            if self.rank[root_x] < self.rank[root_y]:
                self.par[root_y] += self.par[root_x]
                self.par[root_x] = root_y

            else:
                self.par[root_x] += self.par[root_y]
                self.par[root_y] = root_x
                if self.rank[root_x] == self.rank[root_y]:
                    self.rank[root_x]+=1
        
    def same(self,x,y):
        root_x = self.root(x)
        root_y = self.root(y)
        return root_x == root_y 
    
    def size(self,x):
        return -self.par[self.root(x)]

"""
uf = UnionFind(5)
uf.unite(3,4)
uf.unite(1,2)

uf.unite(1,4)
print(uf.size_dict)
"""
def solve(edges,N,M):
 
    score= N*(N-1)//2
    outputs = [score]
    uf = UnionFind(N)
    for edge in edges[::-1]:
        if not uf.same(*edge):
            score -= uf.size(edge[0]) * uf.size(edge[1])
            uf.unite(*edge)
        outputs.append(score)
    for i in range(M):
        print(int(outputs[M-i-1]))

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

N,M,edges = get_input()
# = 10**6
#M=10**5
#import numpy as np
#edges = [(np.random.randint(N),np.random.randint(N)) for i in range(M)]
solve(edges,N,M)
if N==100:
    print((N+1)*pow(100, D))
else:
    print(N*pow(100, D))

### FIXED CODE ###

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

if not N==100:
    print(N*pow(100, D))
else:
    print(101*pow(100, D))
N = input()
s = 0
for i in range(len(N)):
    n = int(N[i])
    s += n
if int(N) % s == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

d,N = map(int,input().split())
if N != 100:
    print((100**d)*N)
else:
    print((100**d)*101)
l = list(map(int,input().sprit()))
a = l[0]
b = l[1]
if b == 1:
    print(0)
else:
    print((b-1//a)+1)


### FIXED CODE ###

l = list(map(int,input().split()))
a = l[0]
b = l[1]
if b == 1:
    print(0)
else:
    if (b-1)%(a-1) == 0:
        print((b-1)//(a-1))
    else:
        print((b-1)//(a-1)+1)