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

import sys
sys.setrecursionlimit(10**8)
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
  a,b,c = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

def dfs(v):
  if len(edge[v])==0:
    return 0
  for u in edge[v]:
    if visited[u]==False:
      visited[u]=True
      dfs(u)
  return 0

ans = 0
visited = [False]*N
for i in range(N):
  if visited[i]==False:
    visited[i]=True
    dfs(i)
    ans += 1
print(ans)

### FIXED CODE ###

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

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
            x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

uf = UnionFind(N)

for _ in range(M):
  x,y,z = map(int, input().split())
  uf.union(x-1,y-1)
  
ans = len(uf.roots())
  
print(ans)
### BUGGY CODE ###

import sys
from bisect import bisect_left
inpurt = sys.stdin.readline
a, b, q = map(int, input().split())
INF = 10 ** 11
s = [-INF]
for i in range(a):
    si = int(input())
    s.append(si)
s.append(INF)
t = [-INF]
for i in range(b):
    ti = int(input())
    t.append(ti)
t.append(INF)
x = []
for i in range(q):
    xi = int(input())
    x.append(xi)

for xi in x:
    index_s = bisect_left(s, xi)
    s1 = abs(xi - s[index_s - 1])
    s2 = abs(xi - s[index_s])
    index_t = bisect_left(t, xi)
    t1 = abs(xi - t[index_t - 1])
    t2 = abs(xi - t[index_t])
    print(min(max(s1, t1), max(s2, t2), min(s1, t2) * 2 + max(s1, t2), min(s2, t1) * 2 + max(s2, t1)))


### FIXED CODE ###

import sys
from bisect import bisect_left
inpurt = sys.stdin.readline
a, b, q = map(int, input().split())
INF = 10 ** 11
s = [-INF]
s_append = s.append
for i in range(a):
    si = int(input())
    s_append(si)
s_append(INF)
t = [-INF]
t_append = t.append
for i in range(b):
    ti = int(input())
    t_append(ti)
t_append(INF)
x = []
x_append = x.append
for i in range(q):
    xi = int(input())
    x_append(xi)

for xi in x:
    index_s = bisect_left(s, xi)
    s1 = xi - s[index_s - 1]
    s2 = s[index_s] - xi
    index_t = bisect_left(t, xi)
    t1 = xi - t[index_t - 1]
    t2 = t[index_t] -xi
    print(min(max(s1, t1), max(s2, t2), min(s1, t2) * 2 + max(s1, t2), min(s2, t1) * 2 + max(s2, t1)))
### BUGGY CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
bc = [list(map(int, input().split())) for _ in range(m)]
for b, c in bc:
    for _ in range(b):
        x = heapq.heappop(a)
        if c > x:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, x)
print(sum(a))


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
bc = [list(map(int, input().split())) for _ in range(m)]
bc = sorted(bc, key=lambda x: -x[1])
for b, c in bc:
    for _ in range(b):
        x = heapq.heappop(a)
        if c > x:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, x)
            break
print(sum(a))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

N,K = map(int,input().split())
P = [ i-1 for i in list(map(int,input().split())) ]
C = list(map(int,input().split()))

g = [ [] for _ in range(N) ]
for i in range(N):
  g[i].append(P[i])

def dfs(i):
  global cycle
  nei = g[i][0]
  if nei in cycle: return
  cycle.append(nei)
  dfs(nei)

cycles = []

for i in range(N):
  cycle = []
  dfs(i)
  c = [ C[j] for j in cycle ]
  cycles.append(c) 

ans = -float('inf')
for i in range(N):
  c = cycles[i]
  cum = c[::]
  for j in range(1,len(c)):
    cum[j] = cum[j-1] + cum[j]

  if cum[-1] < 0:
    ans = max(ans, max(cum[0:K]))
  else:
    t = K//len(c)
    r = K - t*len(c)
    cum = [0]+cum[::]
    ans = max(ans, cum[-1]*t+max(cum[:r+1]))

print(ans)



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N,K = map(int,input().split())
P = [ i-1 for i in list(map(int,input().split())) ]
C = list(map(int,input().split()))
ans = -float('inf')

for i in range(N):
  cycle = []
  tot = 0
  nex = i
  while True:
    nex = P[nex]
    cycle.append(C[nex])
    tot += C[nex]
    if nex == i: break

  l = len(cycle)
  t = 0
  for j in range(l):
    t += cycle[j]
    if j+1 > K: break
    now = t
    if tot > 0:
      now += tot*((K-(j+1))//l)
    ans = max(ans, now)

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

n=int(input())
s=[""]*n
st=set()
r=0
for ii in range(n):
  ss=list(input())
  ss.sort()
  ss="".join(ss)
  s[ii]=ss
  st.add(ss)

if len(st)==n:
  print(0)
  exit()
if len(st)==1:
  print((n*(n-1))//2)
  exit()

tp=[[""]*2 for ii in range(len(st))]
ii=0
for sss in st:
  tp[ii][0]=s.count(sss)
  tp[ii][1]=sss
  ii+=1
tp.sort(reverse=True)
"""
for ii in range(len(tp)):
  print(tp[ii])
"""
for jj in range(len(tp)):
  if tp[jj][0]==1:
    print(r)
    exit()
  """sss=tp[jj][1]
  ls=[]
  r2=0
  for ii in range(len(s)):
    if s[ii]==sss:
      ls.append(ii)
      r2+=1
  m=len(ls)
  for ii in range(m):
    del s[ls[m-1-ii]]
  """
  r2=tp[jj][0]
  if r2>1:
    r+=(r2*(r2-1))//2      
    
print(r)

### FIXED CODE ###

n=int(input())
s=[""]*n
st=set()
d={}
for ii in range(n):
  ss=list(input())
  ss.sort()
  ss="".join(ss)
  if ss in st:
    d[ss]+=1
  else:
    d[ss]=1
    st.add(ss)

if len(st)==n:
  print(0)
  exit()
if len(st)==1:
  print((n*(n-1))//2)
  exit()

r=0
for sss in st:
  c=d[sss]
  if c>1:
    r+=(c*(c-1))//2
    
print(r)
### BUGGY CODE ###

# 部分リストのリスト
def all_sublist(lst):
    lstlst = []
    for i in range(2**len(lst)):
        sublst = []
        for j in range(len(lst)):
            if (i >> j) & 1 == 1:
                sublst.append(lst[j])
        lstlst.append(sublst)
    return lstlst


# 入力
H, W, K = map(int, input().split())
S = [[int(x) for x in list(input())] for h in range(H)]

# 横方向にカットする位置の列挙
cutlst = all_sublist(list(range(1, H)))

# 横方向の切り方を動かして切る数の合計の最小値を求める
cnt_min = 10**9 + 7
for cut in cutlst:
    # 横方向に切って圧縮したものをSSとする
    SS = []
    cut.append(H)
    start = 0
    for stop in cut:
        T = []
        for w in range(W):
            tmp = 0
            for h in range(start, stop):
                tmp += S[h][w]
            T.append(tmp)
        SS.append(T)
        start = stop
    H0 = len(SS)
    # K以上の成分があったらこのcutはパス
    if any([SS[h][w] > K for h in range(H0) for w in range(W)]):
        continue
    # 縦方向に切る数を数える
    cnt = len(cut) - 1
    left = [0 for h in range(H0)]
    right = [SS[h][0] for h in range(H0)]
    for w in range(1, W):
        left, right = right, [right[h] + SS[h][w] for h in range(H0)]
        leftOK = all([left[h] <= K for h in range(H0)])
        rightNG = any([right[h] > K for h in range(H0)])
        # すべての成分がK以下になるギリギリのところで切る
        if leftOK and rightNG:
            left = [0 for h in range(H0)]
            right = [SS[h][w] for h in range(H0)]
            cnt += 1
    cnt_min = min(cnt_min, cnt)
print(cnt_min)


### FIXED CODE ###

# 部分リストのリスト
def all_sublist(lst):
    lstlst = []
    for i in range(2**len(lst)):
        sublst = []
        for j in range(len(lst)):
            if (i >> j) & 1 == 1:
                sublst.append(lst[j])
        lstlst.append(sublst)
    return lstlst


# 入力
H, W, K = map(int, input().split())
S = [[int(x) for x in list(input())] for h in range(H)]

# 横方向にカットする位置の列挙
cutlst = all_sublist(list(range(1, H)))

# 横方向の切り方を動かして切る数の合計の最小値を求める
cnt_min = 10**9 + 7
for cut in cutlst:
    # 横方向に切って圧縮したものをSSとする
    SS = []
    cut.append(H)
    start = 0
    for stop in cut:
        T = []
        for w in range(W):
            tmp = 0
            for h in range(start, stop):
                tmp += S[h][w]
            T.append(tmp)
        SS.append(T)
        start = stop
    H0 = len(SS)
    # K以上の成分があったらこのcutはパス
    if any([SS[h][w] > K for h in range(H0) for w in range(W)]):
        continue
    # 縦方向に切る数を数える
    cnt = len(cut) - 1
    left = [0 for h in range(H0)]
    right = [SS[h][0] for h in range(H0)]
    for w in range(1, W):
        left, right = right, [right[h] + SS[h][w] for h in range(H0)]
        leftOK = all([left[h] <= K for h in range(H0)])
        rightNG = any([right[h] > K for h in range(H0)])
        # すべての成分がK以下になるギリギリのところで切る
        if leftOK and rightNG:
            left = [0 for h in range(H0)]
            right = [SS[h][w] for h in range(H0)]
            cnt += 1
    cnt_min = min(cnt_min, cnt)
print(cnt_min)
### BUGGY CODE ###

N=int(input())
*A,=tuple(map(int,input().split()))

for i in range(1,N+1):
    print(A.count(i))

### FIXED CODE ###

N=int(input())
*A,=sorted(map(int,input().split()))

import bisect

for i in range(1,N+1):
    print(bisect.bisect_right(A,i)-bisect.bisect_left(A,i))
### BUGGY CODE ###

from collections import deque
def inpl(): return list(map(int, input().split()))

N, M = inpl()
G = {i:[] for i in range(N)}
X = [0]*(N)
searched = [0]*(N)
pairents = [-1]*N

for _ in range(N-1+M):
    a, b = inpl()
    G[a-1].append(b-1)
    X[b-1] += 1

q = X.index(0)

Q = deque([q])
while Q:
    p = Q.pop()
    for q in G[p]:
        if searched[q] <= searched[p]:
            searched[q] = searched[p] + 1
            Q.append(q)

for a in range(N):
    for b in G[a]:
        if searched[b] == searched[a] + 1:
            pairents[b] = a
for p in pairents:
    print(p+1)
    

### FIXED CODE ###

from collections import deque
def inpl(): return list(map(int, input().split()))

N, M = inpl()
G = {i:[] for i in range(N)}
rG = {i: [] for i in range(N)}
X = [0]*(N)
searched = [0]*(N)

for _ in range(N-1+M):
    a, b = inpl()
    G[a-1].append(b-1)
    rG[b-1].append(a-1)
    X[b-1] += 1

q = X.index(0)
T = [0]*N
Q = deque([q])
t = 0
while Q:
    p = Q.popleft()
    T[p] = t
    t += 1
    for q in G[p]:          
        X[q] -= 1
        if X[q] == 0:
            Q.append(q)

for i in range(N):
    c, ans = -1, 0
    for p in rG[i]:
        if c < T[p]:
            c, ans = T[p], p+1
    print(ans)
### BUGGY CODE ###

import numpy as np
N ,K = list(map(int, input().split()))
p = np.array(list(map(int, input().split())))
pline=[]
for i in range(N-K+1):
  num = np.array(list(map(lambda x: (x+1)/2, p[i:i+K])))
  pline.append(num.sum())
print(max(pline))

### FIXED CODE ###

N ,K = list(map(int, input().split()))
p = list(map(lambda x: (1+int(x))/2, input().split()))
s = [0]*N
s[0]=p[0]
for i in range(1,N):
  s[i] = s[i-1]+p[i]

l = [s[K-1]]
for i in range(N-K):
  l.append(s[i+K]-s[i])

print(max(l))
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
s = []

for k in range(min(a), max(a) + 1):
	tmp = 0
	for x in a:
		if x in [k - 1, k, k + 1]:
			tmp += 1
	s.append(tmp)
print(max(s))


### FIXED CODE ###

from bisect import bisect_left, bisect_right

N = int(input())
a = sorted(list(map(int, input().split())))

ans = 1
for i in range(N):
    X = a[i]
    res = bisect_right(a, X+1) - bisect_left(a, X-1)
    ans = max(res, ans)

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

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

root1 = {}
root2 = {}
   
for i in range(m):
    u, v, a, b = map(int, input().split())
    root1[(u, v)] = a
    root2[(u, v)] = b

def edge(G, x):
    return([(b, G[(a, b)]) for (a, b) in G if a == x] + [(a, G[(a, b)]) for (a, b) in G if b == x])

def min_cost(G, start, end):
    S = {start: 0}
    D = {}
    while len(S) > 0:
        x = select_min(S)
        m = S[x]
        del S[x]
        D[x] = m
        for (y, w) in edge(G, x):
            if y in S:
                if S[y] > m + w:
                    S[y] = m + w
            elif y not in D:
                S[y] = m + w
    return D[end]

def select_min(S):
    m = -1
    for a in S:
        if m == -1 or m > S[a]:
            x = a
            m = S[a]
    return x

cost = []
for i in range(n):
    cost.append(min_cost(root1, s, i + 1) + min_cost(root2, i + 1, t))

for i in range(n):
    print(10 ** 15 - min(cost[i:]))

### FIXED CODE ###

import heapq

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

root1 = []
for i in range(n):
    root1.append({})
root2 = []
for i in range(n):
    root2.append({})
   
for i in range(m):
    u, v, a, b = map(int, input().split())
    root1[u - 1][v] = a
    root1[v - 1][u] = a
    root2[u - 1][v] = b
    root2[v - 1][u] = b

def min_cost(root, start): # 経路の端点を１つ指定して任意の点への最小コストを計算
    S = [[0, start]]
    heapq.heapify(S)
    D = [float("inf")] * n
    D[start - 1] = 0
    while len(S) > 0:
        cost, site = heapq.heappop(S)
        if D[site - 1] < cost:
            continue
        for site2, cost2 in root[site - 1].items():
            if D[site2 - 1] > cost + cost2:
                D[site2 - 1] = cost + cost2
                heapq.heappush(S, [cost + cost2, site2])
    return D

jpy = min_cost(root1, s) # 円で両替地点まで移動する最小コスト
snuke = min_cost(root2, t) # 両替地点からスヌークで移動する最小コスト
cost = [jpy[i] + snuke[i] for i in range(n)] # 両替地点についてループ

minimum_cost = []
temp_min = cost[n - 1]
for i in reversed(range(n)):
    temp_min = min(temp_min, cost[i])
    minimum_cost.append(temp_min)

for i in reversed(range(n)):
    print(10 ** 15 - minimum_cost[i])
### BUGGY CODE ###

X,Y,Z,K = map(int,input().split(' '))
A = list(map(int, input().split(' ')))
B = list(map(int, input().split(' ')))
C = list(map(int, input().split(' ')))

list.sort(A, reverse=True)
list.sort(B, reverse=True)
list.sort(C, reverse=True)

sums = []
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if (i+1)*(j+1)*(k+1) <= K:
                sums.append(A[i]+B[j]+C[k])

list.sort(sums, reverse=True)
for i in range(K):
    print(sums[i])

### FIXED CODE ###

X,Y,Z,K = map(int,input().split(' '))
A = list(map(int, input().split(' ')))
B = list(map(int, input().split(' ')))
C = list(map(int, input().split(' ')))

list.sort(A, reverse=True)
list.sort(B, reverse=True)
list.sort(C, reverse=True)

sums = []
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if (i+1)*(j+1)*(k+1) > K:
                break
            sums.append(A[i]+B[j]+C[k])

for a in sorted(sums, reverse=True)[:K]:
    print(a)
### BUGGY CODE ###

#import sys
#input=sys.stdin.readline
from collections import Counter
n=int(input())
A=tuple(input().split())
C=Counter(A)
c1,c2,c3=[C[s] for s in ('1','2','3')]
DP=[[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
for i in range(c3+1):
    for j in range(c3+c2-i+1):
        for k in range(n-i-j+1):
            if i==j==k==0:
                continue
            tmp=n
            if i>0:
                tmp+=DP[k][j+1][i-1]*i
            if j>0:
                tmp+=DP[k+1][j-1][i]*j
            if k>0:
                tmp+=DP[k-1][j][i]*k
            DP[k][j][i]=tmp/(i+j+k)
print(DP[c1][c2][c3])

### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import Counter
n=int(input())
A=tuple(input().split())
C=Counter(A)
c1,c2,c3=[C[s] for s in ('1','2','3')]
DP=[[[0.0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
for i in range(c3+1):
    for j in range(c3+c2-i+1):
        for k in range(n-i-j+1):
            if i==j==k==0:
                continue
            tmp=n
            if i>0:
                tmp+=DP[k][j+1][i-1]*i
            if j>0:
                tmp+=DP[k+1][j-1][i]*j
            if k>0:
                tmp+=DP[k-1][j][i]*k
            DP[k][j][i]=tmp/(i+j+k)
print(DP[c1][c2][c3])
### BUGGY CODE ###

def search(a):
    x=0
    a="0"*(3-len(a))+a
    for i in range(n):
        if a[x]==s[i]:
            x+=1
            if x==3:
                return True
    return False
n=int(input())
s=input()
ans=0
k=[False]*1000
for i in range(1000):
    k[i]=search(str(i))
for i in k:
    if i:
        ans+=1
print(ans)

### FIXED CODE ###

def search(a):
    x=0
    a="".join(["0"*(3-len(a)),a])
    for i in range(n):
        if a[x]==s[i]:
            x+=1
            if x==3:
                return True
    return False
n=int(input())
s=input()
ans=0
k=[False]*1000
for i in range(1000):
    k[i]=search(str(i))
for i in k:
    if i:
        ans+=1
print(ans)
### BUGGY CODE ###

import bisect
n, q = map(int, input().split())
STX = []
for i in range(n):
    s, t, x = map(int, input().split())
    STX.append((s, t, x))
STX.sort(key=lambda _: _[2])
S, T, X = [], [], []
for stx in STX:
    s, t, x = stx
    S.append(s)
    T.append(t)
    X.append(x)
D = [int(input()) for j in range(q)]
A = [-1 for j in range(q)]
st = set()
for i in range(n):
    l = bisect.bisect_left(D, S[i]-X[i])
    r = bisect.bisect_left(D, T[i]-X[i])
    lr = set(range(l, r))
    for j in lr.difference(st):
        A[j] = X[i]
    st = st.union(lr)
for a in A:
    print(a)


### FIXED CODE ###

import bisect
n, q = map(int, input().split())
STX = []
for i in range(n):
    s, t, x = map(int, input().split())
    STX.append((s, t, x))
STX.sort(key=lambda _: _[2])
S, T, X = [], [], []
for stx in STX:
    s, t, x = stx
    S.append(s)
    T.append(t)
    X.append(x)
D = [int(input()) for j in range(q)]
A = [-1 for j in range(q)]
B = [-1 for j in range(q)]
for i in range(n):
    l = bisect.bisect_left(D, S[i]-X[i])
    r = bisect.bisect_left(D, T[i]-X[i])
    while l < r:
        if B[l] == -1:
            A[l] = X[i]
            B[l] = r
            l += 1
        else:
            l = B[l]
print(*A, sep='\n')
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
for _ in range(m):
  b, c = map(int, input().split())
  for i in range(b):
    if a[i] < c:
      a[i] = c
  a = sorted(a)
print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
bc = [list(map(int, input().split())) for _ in range(m)]
bc = sorted(bc, key=lambda x:x[1], reverse=True)
st = 0
flag = True
for i in range(m):
  b, c = bc[i]
  if flag and st < n:
    for i in range(st, min(b+st, n)):
      if a[i] < c:
        a[i] = c
      else:
        flag = False
        break
    st += b
  else:
    break

print(sum(a))
### BUGGY CODE ###

import os, sys, atexit
from io import BytesIO, StringIO
 
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
_OUTPUT_BUFFER = StringIO()
sys.stdout = _OUTPUT_BUFFER
 
@atexit.register
def write():
    sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
import math 
def factors(n):
    fact = []
    i = 1
    while i <= math.sqrt(n): 
        if (n % i == 0) : 
            if (n / i == i):
                fact.append(i) 
            else:
                fact.append(i)
                fact.append(n // i)
        i = i + 1
    return fact
n = int(input())
l = list(map(int, input().split()))
vis = [0] * 1000003
ans = 0
for i in l: vis[i] -= -1
for i in range(n):
    tmp = factors(l[i])
    check = 0
    for j in tmp:
        if vis[j]:
            if j == l[i] and vis[j] > 1: check = 1
            elif j != l[i] and vis[j] > 0: check = 1
        if check: break
    if check == 0: ans -= -1
print(ans)

### FIXED CODE ###

import os, sys, atexit
from io import BytesIO, StringIO
 
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
_OUTPUT_BUFFER = StringIO()
sys.stdout = _OUTPUT_BUFFER
 
@atexit.register
def write():
    sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
n = int(input())
l = list(map(int, input().split()))
l.sort()
vis = [0] * 1000004
for i in l: vis[i] -= -1
for i in range(n):
    tmp = l[i]
    while tmp <= l[n - 1]:
        if vis[tmp]:
            if tmp == l[i]:
                if vis[tmp] > 1: vis[tmp] = 0
            else:
                vis[tmp] = 0
        tmp += l[i]
ans = 0
for i in vis: ans += i
print(ans)
### BUGGY CODE ###

N=int(input())
S=[]
for n in range(N):
    s=sorted(list(input()))
    s=''.join(s)
    S.append(s)

import itertools
ans=0
for s1,s2 in list(itertools.combinations(S,2)):
    if s1==s2:
        ans+=1
print(ans)


### FIXED CODE ###

N=int(input())
S={}
c={}
for i in range(N):
    s=''.join(sorted(input()))  
    if s in S:
        c[s]+=1
        if c[s]>=2:
            S[s]=S[s]+c[s]
        else:
            S[s]+=1

    else:
        S[s]=0
        c[s]=0
print(sum(S.values()))
### BUGGY CODE ###

s = input()
N = int(input())
S = []
order = 1
for _ in range(N):
    res = input().split()
    if res[0] == "1":
        order = order * - 1
    elif res[1] == "1":
        if order == 1:
            s = res[2]+s
        else:
            s = s+res[2]
    else:
        if order == 1:
            s = s+res[2]
        else:
            s = res[2]+s

if order == -1:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

from collections import deque
s = input().split()
sd = deque()
for i in s:
    sd.append(i)
N = int(input())
S = []
order = 1
for _ in range(N):
    res = input().split()
    if res[0] == "1":
        order = order * - 1
    elif res[1] == "1":
        if order == 1:
            sd.appendleft(res[2])
        else:
            sd.append(res[2])
    else:
        if order == 1:
            sd.append(res[2])
        else:
            sd.appendleft(res[2])

sd_str="".join(list(sd))
if order == -1:
    print(sd_str[::-1])
else:
    print(sd_str)
### BUGGY CODE ###

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

ans = 0

for i in range(N):
    for j in range(i+1):
        if P[i] > P[j]:
            break
        else:
            if j == i:
                ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
P_min = []
a = 200000
ans = 0

for i in range(N):
    if a >= P[i]:
        ans += 1
        a = P[i]

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

import sys
sys.setrecursionlimit(10**9)
n,m=map(int, input().split())

g=[[] for i in range(n)]
x=[[] for i in range(m)]

count=0
ans=0
for i in range(m):
    u,v=map(int,input().split())
    u-=1
    v-=1
    g[u].append(v)
    g[v].append(u)
    x[i]=[u,v]
    
memo=[False for i in range(n)]

def dfs(now,prev):
    for next in g[now]:
        if next!=prev:
            if memo[next]==True:
                continue
            else:
                memo[next]=True
                dfs(next,now)


for i in range(m):
    g[x[i][0]].remove(x[i][1])
    g[x[i][1]].remove(x[i][0])
    for j in range(n):
        memo[j]=True
        dfs(j,-1)
        ans+=memo.count(False)
        memo=[False for i in range(n)]
    print(ans//2)
    ans=0

    
    
    
    
    




### FIXED CODE ###

# ユニオンファインド
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def cmb(n, r):
    if (r < 0 or r > n):
        return 0
    r=min(r,n-r)

    return g1[n] * g2[r] * g2[n - r] % mod

def comb(n):
    x=1
    y=1
    for i in range(2):
        x*=(n-i)
        y*=(i+1)
    return x//y


n,m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
b = [[] for i in range(n)]
uf = UnionFind(n)

ans=[]
x=comb(n)
for i in range(m):
    ans.append(x)
    if uf.same(a[m-i-1][0]-1,a[m-i-1][1]-1):
        uf.union(a[m-i-1][0]-1,a[m-i-1][1]-1)
    else:
        x-=uf.size(a[m-i-1][0]-1)*uf.size(a[m-i-1][1]-1)
        uf.union(a[m-i-1][0]-1,a[m-i-1][1]-1)
for i in range(m):
    print(ans[-1-i])