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

from collections import defaultdict as dd
import sys
sys.setrecursionlimit(10 ** 6)
N, Q = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
  
res = [0] * (N + 1)
for _ in range(Q):
  p, x = map(int, input().split())
  res[p] += x
visited = [0] * (N + 1)
def dfs(n):
  global visited
  global res
  visited[n] = 1
  for o in e[n]:
    if visited[o] == 0:
      res[o] += res[n]
      dfs(o)
dfs(1)
sen = ""
for i in range(1, N + 1):
  sen += str(res[i])
  if i != N:
    sen += " "
print(sen)


### FIXED CODE ###

from collections import defaultdict as dd
from collections import deque as dq
N, Q = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
  
res = [0] * (N + 1)
for _ in range(Q):
  p, x = map(int, input().split())
  res[p] += x
visited = [0] * (N + 1)
Q = dq([])
Q.append(1)
visited[1] = 1
while len(Q) != 0:
  n = Q.pop()
  visited[n] = 1
  for o in e[n]:
    if visited[o] == 0:
      res[o] += res[n]
      Q.append(o)
#def dfs(n):
#  global visited
#  global res
#  visited[n] = 1
#  for o in e[n]:
#    if visited[o] == 0:
#      res[o] += res[n]
#      dfs(o)
#dfs(1)
sen = ""
for i in range(1, N + 1):
  sen += str(res[i])
  if i != N:
    sen += " "
print(sen)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

def dijkstra(s,N,cost):
    d = [float('inf')] * N
    used = [False] * N
    d[s] = 0

    while True:
        v = -1
        for i in range(N):
            if (not used[i]) and (v == -1 or d[i] < d[v]):
                v = i
        
        if v == -1:
            break
        
        used[v] = True
        for j in range(N):
            d[j] = min(d[j], d[v] + cost[v][j])
    return d


def main():
    N  = int(input())
    cost = [[float('inf')] * N for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        cost[u][v] = w
        cost[v][u] = w

    d = dijkstra(0,N,cost)

    for i in range(N):
        if d[i] % 2 == 0:
            print(0)
        else:
            print(1)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge,N):
    d = [float('inf')] * N
    used = [True] * N
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist, a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

def main():
    N = int(input())
    edge = [[] for i in range(N)]

    for i in range(N-1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append([w,v])
        edge[v].append([w,u])

    D = dijkstra_heap(0,edge,N)
    first = D[0]
    for d in D:
        if abs(d - first) % 2 == 0:
            print(0)
        else:
            print(1)

main()
### BUGGY CODE ###

from operator import itemgetter
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = []

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E.append((D_i, i, -1))
        D[C[i]] = i
    x = len(E)
    E += [0] * Q
    for i in range(Q):
        l, r = map(int, input().split())
        E[x + i] = (l - 1, r - 1, i)

    E.sort(key=lambda tup: tup[0], reverse=True)

    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for e in E:
        if e[2] == -1:
            d.add(e[1], 1)
        else:
            ANS[e[2]] = e[1] - e[0] + 1 - d.sum(e[1])

    for i in range(Q):
        print(ANS[i])

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = defaultdict(list)

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E[D_i].append((D_i, i))
        D[C[i]] = i

    F = defaultdict(list)
    for i in range(Q):
        l, r = map(int, input().split())
        F[l-1].append((r - 1, i))



    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for x in range(N - 1, -1, -1):
        for e in E[x]:
            d.add(e[1], 1)
        for f in F[x]:
            ANS[f[1]] = f[0] - x + 1 - d.sum(f[0])

    for i in range(Q):
        print(ANS[i])

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

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
  dp[i]=dp[i-1]+abs(h[i-1]-h[i])
  for j in range(2,min(k+1,i+1)):
    dp[i]=min(dp[i],dp[i-j]+abs(h[i-j]-h[i]))
print(dp[-1])

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
  kk=max(i-k,0)
  dp[i]=min(d+abs(hh-h[i])for d,hh in zip(dp[kk:i],h[kk:i]))
print(dp[n-1])
### BUGGY CODE ###

from scipy.misc import comb
n,a,b=map(int, input().split())
if n==2:
    print(0)
else:
    ans=2**n-1-comb(n,a,exact=True)-comb(n,b,exact=True)
    print(ans%(10**9+7))

### FIXED CODE ###

n,a,b=map(int, input().split())
 
def comb(n, r,MOD):
    p, q = 1, 1
    for i in range(r):
        p = p * (n-i) % MOD
        q = q * (i+1) % MOD
    return p * pow(q, MOD-2, MOD) % MOD

mod=10**9+7
    
A=comb(n,a,mod)
B=comb(n,b,mod)  
C=pow(2,n,mod)

if n==2:
    print(0)
else:
    print((C-1-A-B)%mod)
### BUGGY CODE ###

N = int(input())
p = 1
for i in range(N):
  p *= i+1
print(p % (pow(10, 9) + 7))


### FIXED CODE ###

N = int(input())
p = 1
for i in range(N):
  p *= i+1
  p = p % (pow(10, 9) + 7)
print(p)
### BUGGY CODE ###

s = input()
t = input()

for c in t:
    if c not in s:
        print(-1)
        exit()

i = 0
mod = len(s)
for c in t:
    while True:
        if s[i % mod] == c:
            i += 1
            break
        else:
            i += 1
    
print(i)


### FIXED CODE ###

from bisect import bisect

def indexes(L, x):
    INDEXES = []
    for i in range(len(L)):
        if L[i] == x:
            INDEXES.append(i)
    return INDEXES


s = input()
t = input()

ss = s * 2
alphabets = "abcdefghijklmnopqrstuvwxyz"
INDEXES = {c:indexes(ss, c) for c in alphabets}

def index(i, c):
    return INDEXES[c][bisect(INDEXES[c], i)]

if not INDEXES[t[0]]:
    print(-1)
    exit()
now = INDEXES[t[0]][0]

answer = now + 1
mod = len(s)
for c in t[1:]:
    if not INDEXES[c]:
        print(-1)
        exit()
    next = index(now, c)
    answer += next - now
    now = next % mod

print(answer)
### BUGGY CODE ###

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

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

dp[0][0][0] = 1
for i in range(1, N+1):
    for j in range(N+1):
        for k in range(50*N+1):
            dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-X[i-1]]

ans = 0
for i in range(1, N+1):
    ans += dp[N][i][A * i]
print(ans)


### FIXED CODE ###

N, A = map(int,input().split())
X = list(map(int,input().split()))
dp = [[[0 for _ in range(50*50 + 1)] for _ in range(N+1)] for _ in range(N+1)]

dp[0][0][0] = 1
for i in range(1, N+1):
    for j in range(i+1):
        for k in range(50*j+1):
            dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-X[i-1]]

ans = 0
for i in range(1, N+1):
    ans += dp[N][i][A * i]
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
# Atcoder necoak answer
# https://atcoder.jp/contests/abc165/tasks/abc165_c

import numpy as np

def create_list(tmp_anslist, zan_length, zan_num_list):
    if zan_length == 0:
        anslist_candidates.append(tmp_anslist)
        return 
    
    for i, num in enumerate(zan_num_list):
        more_zan_num_list = zan_num_list[i:]
        create_list(tmp_anslist + [num], zan_length-1, more_zan_num_list)

in_nmq=input()
in_n, in_m, in_q = in_nmq.split()
N = int(in_n)
M = int(in_m)
Q = int(in_q)

abcd_array = np.empty((Q, 4), dtype=int)

for i in range(Q):
    in_abcd = input()
    in_a, in_b, in_c, in_d = in_abcd.split()
    a = int(in_a)
    b = int(in_b)
    c = int(in_c)
    d = int(in_d)
    abcd_array[i] = [a, b, c, d]

anslist_candidates = []
create_list([], N, [ax for ax in range(1, M+1)])
# print(anslist_candidates)

max_anslist_indx = 0
max_anslist_score = 0
for indx, tmp_anslist in enumerate(anslist_candidates):
    sum_d = 0
    for ai, bi, ci, di in abcd_array:
        #print('ai:%d, bi:%d, ci:%d, di:%d' % (ai, bi, ci, di))
        #print('tmp_anslist:%s' % (tmp_anslist))
        if ((tmp_anslist[bi-1] - tmp_anslist[ai-1]) == ci):
            sum_d += di
    #print('%s : %d' % (tmp_anslist, sum_d))
    if sum_d > max_anslist_score:
        max_anslist_score = sum_d
        max_anslist_indx = indx

print(max_anslist_score)


### FIXED CODE ###

#!/usr/bin/env python3
# Atcoder necoak answer
# https://atcoder.jp/contests/abc165/tasks/abc165_c

import numpy as np
from itertools import combinations_with_replacement

# def create_list(tmp_anslist, zan_length, zan_num_list):
#     if zan_length == 0:
#         anslist_candidates.append(tmp_anslist)
#         return
#     
#     for i, num in enumerate(zan_num_list):
#         more_zan_num_list = zan_num_list[i:]
#         create_list(tmp_anslist + [num], zan_length-1, more_zan_num_list)

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

# abcd_array = np.empty((Q, 4), dtype=int)
abcd_array = []
for i in range(Q):
    abcd = map(int, input().split())
    abcd_array.append(list(abcd))
# print(abcd_array)

# anslist_candidates = []
# create_list([], N, [ax for ax in range(1, M+1)])
# print(anslist_candidates)

anslist_candidates = combinations_with_replacement(range(1, M+1), N)


max_anslist_score = 0
for tmp_anslist in anslist_candidates:
    sum_d = 0

    is_valid_anslist = True
    prev_ansitem = tmp_anslist[0]
    for ansitem in tmp_anslist[1:]:
        if prev_ansitem > ansitem:
            is_valid_anslist = False
            break
    if not is_valid_anslist:
        continue

    for ai, bi, ci, di in abcd_array:
        #print('ai:%d, bi:%d, ci:%d, di:%d' % (ai, bi, ci, di))
        #print('tmp_anslist:%s' % (tmp_anslist))
        if ((tmp_anslist[bi-1] - tmp_anslist[ai-1]) == ci):
            sum_d += di
    #print('%s : %d' % (tmp_anslist, sum_d))
    max_anslist_score = max(max_anslist_score, sum_d)

print(max_anslist_score)
### BUGGY CODE ###

N, M = input().split(" ")
N, M = int(N), int(M)
H = [int(h) for h in input().split(" ")]
A = []
B = []
for i in range(M):
    a, b = input().split(" ")
    a, b = int(a), int(b)
    A.append(a)
    B.append(b)

cnt = 0
for h in range(len(H)):
    flag = -1
    for m in range(M):
        if A[m] == h+1:      
            if H[B[m]-1] < H[A[m]-1]:
                flag = 1
            else:
                flag = 0
                break
        if B[m] == h+1:
            if H[A[m]-1] < H[B[m]-1]:
                flab = 1
            else:
                flag = 0
                break
    if flag == 1 or flag == -1:
        cnt += 1
print(cnt)

### FIXED CODE ###

N, M = input().split(" ")
N, M = int(N), int(M)
H = [int(h) for h in input().split(" ")]
A = []
B = []
TF = [True] * N
for i in range(M):
    a, b = input().split(" ")
    a, b = int(a), int(b)
    if H[a-1] > H[b-1]:
        if TF[b-1]:
            TF[b-1] = False
    elif H[b-1] > H[a-1]:
        if TF[a-1]:
            TF[a-1] = False
    else:
        TF[b-1] = False
        TF[a-1] = False
            
print(sum(TF))
### BUGGY CODE ###

N = int(input())
S = input()
Q = int(input())

ide_ele = set()

def segfunc(x,y):
    return x|y

def init(init_val):
    #set_val
    for i in range(N):
        seg[i+num-1]=set((init_val[i]))
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#num:n以上の最小の2のべき乗
num =2**(N-1).bit_length()
seg=[ide_ele]*2*num

init(S)

for _ in range(Q):
    t, a, b = input().split()
    if t == '1':
        a = int(a)
        update(a-1, set((b)))
    else:
        a, b = int(a)-1, int(b)
        print(len(query(a,b)))


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
S = input()
Q = int(input())

ide_ele = 0

def segfunc(x,y):
    return x|y

def init(init_val):
    #set_val
    for i in range(N):
        seg[i+num-1]=1<<(ord(init_val[i])-ord('a'))
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    x = 1<<(ord(x)-ord('a'))
    if x == seg[k]: return
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#num:n以上の最小の2のべき乗
num =2**(N-1).bit_length()
seg=[ide_ele]*2*num

init(S)

for _ in range(Q):
    t, a, b = input().split()
    if t == '1':
        a = int(a)
        update(a-1, b)
    else:
        a, b = int(a)-1, int(b)
        print(bin(query(a,b)).count('1'))
### BUGGY CODE ###

import itertools

k, s = map(int, input().split())
A = [i for i in range(k+1)]
ans = 0
for x,y,z in itertools.combinations_with_replacement(A, 3):
  if x+y+z == s:
    n = 0
    if len(set([x,y,z])) == 1:
      n = 1
    elif len(set([x,y,z])) == 2:
      n = 3
    elif len(set([x,y,z])) == 3:
      n = 6
    ans += n
print(ans)

### FIXED CODE ###

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

ans = 0
for right in range(max(s-k, 0), min(s+1, 2*k+1)):
  lower = max(0, right-k)
  upper = min(k, right)
  if right % 2 != 0:
    ans += upper - lower + 1
  else:
    ans += upper - lower + 1
print(ans)
### BUGGY CODE ###

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

for n in range(N):
  print(A.index(n+1)+1,end=" ")

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [0]*N

for n in range(N):
  B[A[n]-1] = n+1
  
print(*B)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

n,q=map(int,input().split())
a=list(map(int,input().split()))

num = 2**(n-1).bit_length()
def segfunc(x, y): return max(x, y)
seg = [0]*(2*num-1)
for i in range(n):
  seg[i+num-1] = a[i]
for i in range(num-2, -1, -1):
  seg[i] = segfunc(seg[2*i+1], seg[2*i+2])
def update(i, x):
  i += num-1
  seg[i] = x
  while i:
    i = (i-1)//2
    seg[i] = segfunc(seg[i*2+1], seg[i*2+2])
def query(l, r):
  l += num-1
  r += num-2
  if l == r:
    return seg[l]
  s = seg[l]
  l += 1
  while r-l > 1:
    if ~l % 2:
      s = segfunc(seg[l], s)
    if r % 2:
      s = segfunc(seg[r], s)
      r -= 1
    l //= 2
    r = (r-1)//2
  if l == r:
    return segfunc(s, seg[l])
  return segfunc(s, segfunc(seg[l], seg[r]))

for _ in range(q):
  t,a,b=map(int,input().split())
  if t==1:
    update(a-1,b)
  if t==2:
    print(query(a-1,b))
  if t==3:
    ng=a-1
    ok=n+1
    while ng+1!=ok:
      mid=(ng+ok)//2
      if query(ng,mid)>=b:ok=mid
      else:ng=mid
    print(ok)

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

n,q=map(int,input().split())
a=list(map(int,input().split()))

num = 2**(n-1).bit_length()
def segfunc(x, y): return max(x, y)
seg = [0]*(2*num-1)
for i in range(n):
  seg[i+num-1] = a[i]
for i in range(num-2, -1, -1):
  seg[i] = segfunc(seg[2*i+1], seg[2*i+2])
def update(i, x):
  i += num-1
  seg[i] = x
  while i:
    i = (i-1)//2
    seg[i] = segfunc(seg[i*2+1], seg[i*2+2])
def query(l, r):
  l += num-1
  r += num-2
  if l == r:
    return seg[l]
  s = seg[l]
  l += 1
  while r-l > 1:
    if ~l % 2:
      s = segfunc(seg[l], s)
    if r % 2:
      s = segfunc(seg[r], s)
      r -= 1
    l //= 2
    r = (r-1)//2
  if l == r:
    return segfunc(s, seg[l])
  return segfunc(s, segfunc(seg[l], seg[r]))

for _ in range(q):
  t,a,b=map(int,input().split())
  if t==1:
    update(a-1,b)
  if t==2:
    print(query(a-1,b))
  if t==3:
    ng=a-1
    ok=n+1
    while ng+1!=ok:
      mid=(ng+ok)//2
      if query(ng,mid)>=b:ok=mid
      else:ng=mid
    print(ok)
### BUGGY CODE ###

def main():
    from bisect import bisect_left
    n,*t=map(int,open(0).read().split())
    c=0
    for k in range(30):
        b=sorted(i%2**-~k for i in t[n:])
        m=0
        for a in[i%2**-~k for i in t[:n]]:
            l,r=bisect_left(b,2**k-a),bisect_left(b,2**-~k-a)
            if 2**k-a<0:
                l=bisect_left(b,(2**k-a)%2**-~k)-n
            m+=r-l
        c+=m%2*2**k
    print(c)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from numpy import array,searchsorted,sum,hstack
    n,*t=map(int,open(0).read().split())
    a,b=array(t[:n],'i4'),array(t[n:],'i4')
    c=0
    for k in range(28,-1,-1):
        l,h=pow(2,k),pow(2,k+1)
        a%=h
        b%=h
        b.sort()
        y=hstack((b-h,b))
        i=searchsorted(y,l-a)
        j=searchsorted(y,h-a)
        m=sum(j-i)
        c+=m%2*l
    print(c)
if __name__=='__main__':
    main()
### BUGGY CODE ###

A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())

ok = False
for i in range(T+1):
    if A + (V*T) >= B + (W*T):
        ok = True

if ok:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())

if V<=W:
    print("NO")
    import sys
    sys.exit()
import math
if abs(B-A)/(V-W) <= T:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

from scipy.sparse.csgraph import floyd_warshall
import sys
input = sys.stdin.readline

N = int(input())
INF = float('inf')
graph = [[INF] * N for _ in range(N)]

for i in range(N):
    graph[i][i] = 0

for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u, v = u - 1, v - 1
    w = w % 2 + 2
    graph[u][v] = w
    graph[v][u] = w

distance = floyd_warshall(graph, directed=False)

print(0)
for i in range(1, N):
    if int(distance[0][i]) % 2 == 0:
        print(0)
    else:
        print(1)

### FIXED CODE ###

import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
read = sys.stdin.read


N = int(readline())
graph = [[] for _ in range(N + 1)]

for i in readlines():
    u, v, w = map(int, i.split())
    graph[u].append((v, w))
    graph[v].append((u, w))

stack = [1]
parent = [0] * (N + 1)
color = [0] * (N + 1)

while stack:
    here = stack.pop()
    for x, w in graph[here]:
        if x == parent[here]:
            continue
        parent[x] = here
        color[x] = color[here] ^ (w % 2)
        stack.append(x)

for i in color[1:]:
    print(i)
### BUGGY CODE ###

# -*- coding utf-8 -*-
###########################
## TLE
###########################

N, M = map(int, input().split())
bridge_m = [set(map(int, input().split())) for _ in range(M)]
bridge_m.append(set())
# print(bridge_m)

def conb2(x):
    return int(x * (x - 1)/2) if x > 1 else 0

sets = []
ans = conb2(N)
ans_list = []
for i in range(M, 0, -1):
    bi = bridge_m[i]
    joint_set = set()
    joint_set = joint_set.union(bi)

    next_sets = []
    for s in sets:
        if not s.isdisjoint(joint_set):
            joint_set = joint_set.union(s)
        else:
            next_sets.append(s)
    next_sets.append(joint_set)

    sets = next_sets

    # calc ans
    ans = conb2(N)
    for s in sets:
        ans -= conb2(len(s))
    # print(ans)
    ans_list.append(ans)


for i in range(M - 1, -1, -1):
    print(ans_list[i])

    

### FIXED CODE ###

# -*- coding utf-8 -*-

N, M = map(int, input().split())
bridge_m = [list(map(int, input().split())) for _ in range(M)]
# print(bridge_m)

class UnionFind():
    def __init__(self, n):
        self.node = [-1] * n
    
    def is_root(self, nid):
        return self.node[nid] < 0

    def find(self, nid):
        # find group id
        if self.is_root(nid):
            return nid
        else:
            self.node[nid] = self.find(self.node[nid])
            return self.node[nid]

    def is_same_group(self, nid1, nid2):
        return self.find(nid1) == self.find(nid2)

    def size(self, nid):
        return - self.node[self.find(nid)]

    def union(self, nid1, nid2):
        if self.is_same_group(nid1, nid2):
            return

        g1 = self.find(nid1)
        g2 = self.find(nid2)
        if self.size(g1) < self.size(g2):
            self.node[g2] -= self.size(g1)
            self.node[g1] = g2
        else:
            self.node[g1] -= self.size(g2)
            self.node[g2] = g1

uf = UnionFind(N + 1)
ans = [0] * M
ans[M - 1] = int(N * (N - 1) / 2)
g_num = 0
for i in range(M - 1, 0, -1):
    a = bridge_m[i][0]
    b = bridge_m[i][1]

    if uf.is_same_group(a, b):
        ans[i - 1] = ans[i]
    else:
        ans[i - 1] = ans[i] - uf.size(a) * uf.size(b)
        uf.union(a, b)

for i in range(M):
    print(ans[i])
### BUGGY CODE ###

N=int(input())
S=[]
count=0
for i in range(N):
    s=sorted(input())
    S.append(s)
for i in range(N):
    for j in range(i+1,N):
        if(S[i]==S[j]):
            count += 1
print(count)

### FIXED CODE ###

N=int(input())
S=[]
count=0
ans=0
for i in range(N):
    s=sorted(input())
    S.append(s)
S.sort()
x=S[0]
for i in range(1,N):
    if(S[i]==x):
        count += 1
    else:
        ans=ans+(count+1)*count//2
        count=0
        x=S[i]
ans=ans+(count+1)*count//2
print(ans)