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

mod = 1000000007


def get_pow():
    cache = {}

    def func(x):
        if x not in cache:
            cache[x] = pow(2, x, mod)
        return cache[x]

    return func


n = int(input())
parents = list(map(int, input().split()))
children = [set() for _ in range(n + 1)]
for c, p in enumerate(parents):
    children[p].add(c + 1)

levels = [{0}]
while True:
    level = set()
    for p in levels[-1]:
        level.update(children[p])
    if not level:
        break
    levels.append(level)
levels.reverse()

level_node_count = []
balls = [None] * (n + 1)

for i, level in enumerate(levels):
    level_node_count.append(len(level))
    for node in level:
        if children[node]:
            balls_from_children = [balls[c] for c in children[node]]
            balls_from_children.sort(key=len)
            for bs1, bs2 in zip(balls_from_children, balls_from_children[1:]):
                for b1, b2 in zip(bs1, bs2):
                    b2[2] = (b1[1] + b1[2]) * b2[1] + b1[2] * b2[0]
                    b2[1] = b1[0] * b2[1] + b1[1] * b2[0]
                    b2[0] *= b1[0]
            for b in balls_from_children[-1]:
                b[0] += b[2]
                b[2] = 0
            balls[node] = [[1, 1, 0]] + balls_from_children[-1]
        else:
            balls[node] = [[1, 1, 0]]

level_node_count.reverse()

pow2 = get_pow()
print(sum(b[1] * pow2(n - l + 1) for l, b in zip(level_node_count, balls[0])) % mod)


### FIXED CODE ###

from collections import deque


def get_pow():
    cache = {}

    def func(x):
        if x not in cache:
            cache[x] = pow(2, x, mod)
        return cache[x]

    return func


mod = 1000000007
n = int(input())
parents = list(map(int, input().split()))
children = [set() for _ in range(n + 1)]
for c, p in enumerate(parents):
    children[p].add(c + 1)

levels = [{0}]
while True:
    level = set()
    for p in levels[-1]:
        level.update(children[p])
    if not level:
        break
    levels.append(level)
levels.reverse()

level_node_count = []
balls = [None] * (n + 1)

for i, level in enumerate(levels):
    level_node_count.append(len(level))
    for node in level:
        cn = children[node]
        if cn:
            if len(cn) == 1:
                bs = balls[cn.pop()]
                bs.appendleft([1, 1, 0])
                balls[node] = bs
                continue
            balls_from_children = [balls[c] for c in children[node]]
            balls_from_children.sort(key=len)
            bs1 = balls_from_children[0]
            for bs2 in balls_from_children[1:]:
                for (b10, b11, b12), b2 in zip(bs1, bs2):
                    b2[2] = ((b11 + b12) * b2[1] + b12 * b2[0]) % mod
                    b2[1] = (b10 * b2[1] + b11 * b2[0]) % mod
                    b2[0] = b2[0] * b10 % mod
                bs1 = bs2
            for b in bs1:
                b[0] = (b[0] + b[2]) % mod
                b[2] = 0
            bs1.appendleft([1, 1, 0])
            balls[node] = bs1
        else:
            balls[node] = deque([[1, 1, 0]])

level_node_count.reverse()

pow2 = get_pow()
print(sum(b[1] * pow2(n - l + 1) % mod for l, b in zip(level_node_count, balls[0])) % mod)
### BUGGY CODE ###

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

ans = 0
for j in range(N):
    original = "RGB"
    if S[j] in original:
        for i in range(j):
            obj = original.replace(S[j], "")
            if S[i] in obj:
                for k in range(j+1, N):
                    if (j-i) != (k-j):
                        obj_2 = obj.replace(S[i], "")
                        if S[k] == obj_2:
                        	ans += 1
print(ans)



### FIXED CODE ###

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

r = S.count("R")
g = S.count("G")
b = S.count("B")

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        k = j + j - i
        if 0 <= k < N:
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                cnt += 1

print(r*g*b - cnt)
### BUGGY CODE ###

from collections import deque

n = int(input())
l = list(map(int, input().split()))

b = deque()
for i in range(n):
    b.append(str(l[i]))
    b.reverse()

print(' '.join(b))

### FIXED CODE ###

from collections import deque

n = int(input())
l = list(map(int, input().split()))

b = deque()
for i in range(n):
    if (n % 2 == 0 and (i+1) % 2 == 0) or (n % 2 != 0 and (i+1) % 2 != 0):
        b.appendleft(l[i])
    else:
        b.append(l[i])

print(' '.join(map(str, b)))
### BUGGY CODE ###

# AtCoder Regular Contest 065
# D - 連結 / Connectivity
# https://atcoder.jp/contests/arc065/tasks/arc065_b
import sys
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parent[x] = y

def main():
    N, *KL = map(int, input().split())
    uf = [UnionFind(N) for _ in range(2)]
    for i in range(2):
        for j in range(KL[i]):
            p, q = map(int, input().split())
            uf[i].union(p-1, q-1)

    d = defaultdict(int)
    for i in range(N):
        d[(uf[0].find(i), uf[1].find(i))] += 1

    # for i in range(N):
    #     print(d[(uf[0].find(i), uf[1].find(i))], end = " ")
    # print("")
    
    print(" ".join([str(d[(uf[0].find(i), uf[1].find(i))]) for i in range(N)]))

if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    main()


### FIXED CODE ###

# AtCoder Regular Contest 065
# D - 連結 / Connectivity
# https://atcoder.jp/contests/arc065/tasks/arc065_b
import sys
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parent[x] = y

def main():
    N, *KL = map(int, input().split())
    uf = [UnionFind(N) for _ in range(2)]
    for i in range(2):
        for j in range(KL[i]):
            p, q = map(int, input().split())
            uf[i].union(p-1, q-1)

    d = defaultdict(int)
    for i in range(N):
        d[(uf[0].find(i), uf[1].find(i))] += 1

    for i in range(N):
        print(d[(uf[0].find(i), uf[1].find(i))], end = " ")
    print("")

if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    main()
### BUGGY CODE ###

import sys
def input():
  return sys.stdin.readline()[:-1]

h, w = map(int, input().split())
s = ['']*(h+2)
s[0] = '#'*(w+2)
for i in range(1, h+1):
  s[i] = '#'+input()+'#'
s[h+1] = '#'*(w+2)

l=[[0]*(w+2) for _ in range(h+2)]
r=[[0]*(w+2) for _ in range(h+2)]
u=[[0]*(w+2) for _ in range(h+2)]
d=[[0]*(w+2) for _ in range(h+2)]
for i in range(1, h+1):
  for j in range(1, w+1):
    if s[i][j]=='.':
      l[i][j]=l[i][j-1]+1
  for j in range(w, 0, -1):
    if s[i][j]=='.':
      r[i][j]=r[i][j+1]+1
for j in range(1, w+1):
  for i in range(1, h+1):
    if s[i][j]=='.':
      u[i][j]=u[i-1][j]+1
  for i in range(h, 0, -1):
    if s[i][j]=='.':
      d[i][j]=d[i+1][j]+1
m=0
for i in range(1, h+1):
  for j in range(1, w+1):
    c=l[i][j]+r[i][j]+u[i][j]+d[i][j]-3
    if m<c:
      m=c
print(m)

### FIXED CODE ###

h, w = map(int, input().split())
s = ['']*(h+2)
s[0] = '#'*(w+2)
for i in range(1, h+1):
  s[i] = '#'+input()+'#'
s[h+1] = '#'*(w+2)

l=[[0]*(w+2) for _ in range(h+2)]
r=[[0]*(w+2) for _ in range(h+2)]
u=[[0]*(w+2) for _ in range(h+2)]
d=[[0]*(w+2) for _ in range(h+2)]
for i in range(1, h+1):
  for j in range(1, w+1):
    if s[i][j]=='.':
      l[i][j]=l[i][j-1]+1
  for j in range(w, 0, -1):
    if s[i][j]=='.':
      r[i][j]=r[i][j+1]+1
for j in range(1, w+1):
  for i in range(1, h+1):
    if s[i][j]=='.':
      u[i][j]=u[i-1][j]+1
  for i in range(h, 0, -1):
    if s[i][j]=='.':
      d[i][j]=d[i+1][j]+1
m=0
for i in range(1, h+1):
  for j in range(1, w+1):
    c=l[i][j]+r[i][j]+u[i][j]+d[i][j]-3
    if m<c:
      m=c
print(m)
### BUGGY CODE ###

import collections
import itertools
N, M = list(map(int, input().split()))
ABs = [list(map(int, input().split())) for _ in range(M)]

ans_list = [0] * (N+1)

dq = collections.deque()

dq.append(1)

print("Yes")
for hoge in range(500000):
    i = dq.popleft()
    iList = [temp for temp in ABs if i in temp]

    iList = list(itertools.chain.from_iterable(iList))
    iList = [temp for temp in iList if iList !=i]

    for hoge in iList:
        if(ans_list[hoge] == 0):
            ans_list[hoge] = i
            dq.append(hoge)


    if(len(dq) == 0):
        break

for ans in ans_list[2:]:
    print(ans)    



### FIXED CODE ###

import collections
import itertools
N, M = list(map(int, input().split()))
ABs = [list(map(int, input().split())) for _ in range(M)]

loads = [[] for _ in range(N+1)]

for AB in ABs:
    loads[AB[0]].append(AB[1])
    loads[AB[1]].append(AB[0])


dq = collections.deque()

dq.append(1)
ans_list = [0 for _ in range(N+1)]

#print(loads)
print("Yes")
while len(dq) != 0:
    i = dq.popleft()

    for vec in loads[i]:
#        print(vec)
        if(ans_list[vec] == 0):
            ans_list[vec] = i
            dq.append(vec)
#        print(ans_list)
#        print(dq)


for ans in ans_list[2:]:
    print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    def chmax(i, j, c, val):dp[i][j][c]=max(dp[i][j][c],val)

    dp = [[[-1] * 4 for _ in range(w+1)] for _ in range(h+1)]
    dp[0][0][0] = 0
    for i in range(h):
        for j in range(w):
            if aa[i][j]:
                for c in range(2,-1,-1):
                    pre = dp[i][j][c]
                    if pre==-1:continue
                    chmax(i,j,c+1,dp[i][j][c]+aa[i][j])
            for c in range(4):
                pre = dp[i][j][c]
                if pre == -1: continue
                chmax(i+1,j,0,pre)
                chmax(i,j+1,c,pre)

    ans = max(dp[h-1][w-1])
    print(ans)

h,w,k=MI()
aa=[[0]*w for _ in range(h)]
for _ in range(k):
    i,j,v=MI()
    aa[i-1][j-1]=v
solve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    dp0 = [0] * (w + 1)
    dp1 = [0] * (w + 1)
    dp2 = [0] * (w + 1)
    dp3 = [0] * (w + 1)
    for i in range(h):
        for j in range(w):
            v = vv[i * w + j]
            if v:
                dp3[j] = max(dp3[j], dp2[j] + v)
                dp2[j] = max(dp2[j], dp1[j] + v)
                dp1[j] = max(dp1[j], dp0[j] + v)
            dp3[j + 1] = max(dp3[j + 1], dp3[j])
            dp2[j + 1] = max(dp2[j + 1], dp2[j])
            dp1[j + 1] = max(dp1[j + 1], dp1[j])
            dp0[j] = max(dp1[j], dp2[j], dp3[j])
    print(dp0[-2])

h, w, k = MI()
vv = [0] * h * w
for _ in range(k):
    i, j, v = MI()
    i, j = i - 1, j - 1
    vv[i * w + j] = v
solve()
### BUGGY CODE ###

import itertools
import numpy as np
from math import factorial
n = list(map(int, input().split()))
x = np.array(list(map(int, input().split())))

x = x - n[1]
b = len(x) - np.count_nonzero(x)
x = [i for i in x if i != 0]

c = 0
for i in range(1, b + 1):
    c += factorial(b) / factorial(i) / factorial(b - i)

cnt = c
for i in range(1, n[0] + 1):
    for j in itertools.combinations(x, i):
        if sum(j) == 0:
            cnt += c + 1
print(int(cnt))

### FIXED CODE ###

import sys
import numpy as np
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()

n, a = imap()
x = np.array(iarr()) - a
MAX = 50*50+1

dp = np.zeros((n+1, 2*MAX+1)).astype(int)
dp[0][MAX] = 1
for i in range(n):
    for j in range(2*MAX):
        if j-x[i] < 0 or j-x[i] > 2*MAX:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = dp[i][j] + dp[i][j-x[i]]
print(dp[n][MAX]-1)
### BUGGY CODE ###

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

N,M = map(int,input().split())
ans=[0]*N
a = [list(map(int, input().split())) for _ in range(N-1)]

for _ in range(M):
    e,f = list(map(int, input().split()))
    ans[e-1] += f

trees = {}
for word in a:
    trees.setdefault(word[0], []).append(word[1])
    trees.setdefault(word[1], []).append(word[0])
    

def sumup(ne,parent):
    global ans
    if ne in trees:    
        for k in trees[ne]:
            if k != parent:
                ans[k-1] += ans[ne-1]
                sumup(k,ne)

sumup(1,0)
for i in ans:
    print(i)


### FIXED CODE ###

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

N,M = map(int,input().split())
ans=[0]*N
a = [list(map(int, input().split())) for _ in range(N-1)]

for _ in range(M):
    e,f = list(map(int, input().split()))
    ans[e-1] += f

trees = {}
for word in a:
    trees.setdefault(word[0], []).append(word[1])
    trees.setdefault(word[1], []).append(word[0])
    

def sumup(ne,parent):
    global ans
    if ne in trees:    
        for k in trees[ne]:
            if k != parent:
                ans[k-1] += ans[ne-1]
                sumup(k,ne)

sumup(1,0)
for i in ans:
    print(i)
### BUGGY CODE ###

def D_11(x):
    n = x[0]  # 整数の数
    a = x[1:]  # 数列
    M = pow(10, 9) + 7  # 求めた解の剰余をこれで取る

    # aの中から重複した要素のインデックス(それぞれl,rとする)を求める
    import collections
    freq = collections.Counter(a).most_common(1)  # 最も多く出てきた数(入力の制約より、頻度は2となる)
    index = [i for i, x in enumerate(a) if x == freq[0][0]]  # 重複した数のインデックスを取得
    l, r = index[0] + 1, index[1] + 1  # +1するのは数列が1スタートのため

    # 組み合わせの計算
    def power(x, n, m):
        # 冪乗(powだと時間がかかりすぎるため)+剰余つき
        y = 1
        while n > 0:
            if n % 2 == 0:
                x = (x * x) % m
                n = n // 2
            else:
                y = (y * x) % m
                n -= 1
        return y

    def mod_combination(n, r, m):
        if r > n:
            return 0
        factrial = [1] * (n + 1)
        inverse = [1] * (n + 1)
        for i in range(1, n + 1, 1):
            factrial[i] = (factrial[i - 1] * i) % m
            inverse[i] = power(factrial[i], m - 2, m)  # フェルマーの小定理からの帰結
        return (factrial[n] * inverse[r] * inverse[n - r]) % m

    for k in range(1, n + 2, 1):
        all_comb = mod_combination(n + 1, k, M)
        duplication = mod_combination(l + n - r, k - 1, M)
        print(all_comb - duplication)

n = int(input())
l = [int(i) for i in input().split()]
x = [n] + l
D_11(x)

### FIXED CODE ###

def D_11(x):
    n = x[0]  # 整数の数
    a = x[1:]  # 数列
    M = 10**9 + 7  # 求めた解の剰余をこれで取る

    s = set()
    result = [x for x in a if x in s or s.add(x)]
    # for x in a:
    # if x in s:
    #     result.append(x)
    # s.add(x) と同じ書き方
    index = [i for i, x in enumerate(a) if x == result[0]]
    l = index[0] + 1
    r = index[1] + 1

    # フェルマーの小定理を用いてコンビネーションを効率よく計算
    factrial = [1] * (n + 2)
    for k in range(1, n + 2):
        factrial[k] = (factrial[k - 1] * k) % M
    fact_inv = [1] * (n + 2)
    fact_inv[n + 1] = pow(factrial[n + 1], M - 2, M)
    for k in range(n, -1, -1):
        fact_inv[k] = (fact_inv[k + 1] * (k + 1)) % M

    def nCr(n, r, M):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factrial[n] * fact_inv[r] * fact_inv[n - r]) % M

    for k in range(1, n + 2):
        print((nCr(n + 1, k, M) - nCr((l - 1) + (n + 1 - r), k - 1, M)) % M)

n = int(input())
l = [int(i) for i in input().split()]
x = [n] + l
D_11(x)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
s=input()
r=0
g=0
b=0
rg=0
gb=0
br=0
ans=1
for i in range(3*n):
    if s[i]=="R":
        if gb:
            ans*=gb
            gb-=1
        elif g:
            ans*=g
            g-=1
            rg+=1
        elif b:
            ans*=b
            b-=1
            br+=1
        else:
            r+=1

    if s[i]=="G":
        if br:
            ans*=br
            br-=1
        elif r:
            ans*=r
            r-=1
            rg+=1
        elif b:
            ans*=b
            b-=1
            gb+=1
        else:
            g+=1
    if s[i]=="B":
        if rg:
            ans*=rg
            rg-=1
        elif g:
            ans*=g
            g-=1
            gb+=1
        elif r:
            ans*=r
            r-=1
            br+=1
        else:
            b+=1

import math

print(ans*math.factorial(n))


### FIXED CODE ###

import sys,math
input=sys.stdin.readline
n=int(input())
s=input()
mod=998244353
r=0
g=0
b=0
rg=0
gb=0
br=0
ans=1
for i in range(3*n):
    if s[i]=="R":
        if gb:
            ans*=gb
            gb-=1
        elif g:
            ans*=g
            g-=1
            rg+=1
        elif b:
            ans*=b
            b-=1
            br+=1
        else:
            r+=1

    if s[i]=="G":
        if br:
            ans*=br
            br-=1
        elif r:
            ans*=r
            r-=1
            rg+=1
        elif b:
            ans*=b
            b-=1
            gb+=1
        else:
            g+=1
    if s[i]=="B":
        if rg:
            ans*=rg
            rg-=1
        elif g:
            ans*=g
            g-=1
            gb+=1
        elif r:
            ans*=r
            r-=1
            br+=1
        else:
            b+=1
    ans%=mod

k=math.factorial(n)
print(ans*k%mod)
### BUGGY CODE ###

import numpy as np
n=int(input())
s=[0]*(n+1)
t=np.zeros(n+1)
h=list(map(int,input().split()))
a=list(map(int,input().split()))
for i in range(n):
    s[h[i]]=t[h[i]]+a[i]
    t[h[i]:]=np.maximum(t[h[i]:],s[h[i]])
print(int(t[-1]))

### FIXED CODE ###

n=int(input())
def f(x):
    s=0
    while x>0:
        s=max(s,t[x])
        x-=x&-x
    return s
def g(x,y):
    while x<n+1:
        t[x]=max(y,t[x])
        x+=x&-x
t=[0]*(n+1)
h=list(map(int,input().split()))
a=list(map(int,input().split()))
for i in range(n):
    g(h[i],f(h[i]-1)+a[i])
print(max(t))
### BUGGY CODE ###

S = input()

flag = 0

words = ("dream","erase","dreamer","eraser")
count = 0

while len(S) >= 5:
    
    for i in words:
        N = len(i)

        if S[-N:] in words:
            n = len(S) - N
            S = S[:n]

            flag = 1
            break
        else:
            continue
 
    if flag == 0:
        break

if len(S) == 0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

S = input()

flag = 0

words = ("dream","erase","dreamer","eraser")
count = 0

while len(S) >= 5:

    for i in words:
        N = len(i)
        if S[-N:] in words:
            n = len(S) - N
            S = S[:n]
            flag = 1
            break
        else:
            flag = 0
            continue


    if flag == 0:
        break



if len(S) == 0:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

# 2019/12/27

h,w=map(int,input().split())
s=[list('#'*(w+2))]
for _ in range(h):
    s+=[list('#'+input()+'#')]
s+=[list('#'*(w+2))]

L=[[0]*(w+2) for _ in range(h+2)]
U=[[0]*(w+2) for _ in range(h+2)]
R=[[0]*(w+2) for _ in range(h+2)]
D=[[0]*(w+2) for _ in range(h+2)]


for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":continue
        L[i][j]=L[i][j-1]+1
        U[i][j]=U[i-1][j]+1

ans=0

for i in range(h,0,-1):
    for j in range(w,0,-1):
        if s[i][j]=="#":continue
        R[i][j]=R[i][j+1]+1
        D[i][j]=D[i+1][j]+1
        lit=L[i][j]+U[i][j]+R[i][j]+D[i][j]-3
        ans=max(ans,lit)
print(ans)

### FIXED CODE ###

# 2019/12/27

h,w=map(int,input().split())
s=[list('#'*(w+2))]
for _ in range(h):
    s+=[list('#'+input()+'#')]
s+=[list('#'*(w+2))]

L,U,R,D=[[[0]*(w+2) for _ in range(h+2)] for _ in range(4)]

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":continue
        L[i][j]=L[i][j-1]+1
        U[i][j]=U[i-1][j]+1

ans=0

for i in range(h,0,-1):
    for j in range(w,0,-1):
        if s[i][j]=="#":continue
        R[i][j]=R[i][j+1]+1
        D[i][j]=D[i+1][j]+1
        lit=L[i][j]+U[i][j]+R[i][j]+D[i][j]-3
        ans=max(ans,lit)
print(ans)
### BUGGY CODE ###

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

B = [list(map(int, input().split())) for _ in range(M)]

class Group:
    id = 0
    def __init__(self):
        self.id = Group.id
        Group.id += 1
        self.count = 1
        self.root = None

    def top(self):
        w = self
        while not w.root is None:
            w = w.root
        return w

    def addMember(self):
        self.count += 1

    def union(self, g):
        self.top().count += g.top().count
        g.top().root = self.top()

    def __repr__(self):
        w = self.top()
        return str(("Gropup", w.id, w.count))

pt = []
G = [Group() for x in range(N+1)]
idx = 0
cnt = 0
while len(B):
    x, y = B.pop()
    wx = G[x]
    wy = G[y]
    if wx.top() is wy.top():
        pt.append(0)
    else:
        pt.append(wx.top().count * wy.top().count)
        wx.union(wy)

    #print(G)

cnt = 0
while len(pt):
    cnt += pt.pop()
    print(cnt)


### FIXED CODE ###

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

pt = []
G = [[None, 1] for x in range(N+1)]

def find(x):
    n = G[x]
    c = []
    while not n[0] is None:
        c.append(n)
        n = n[0]
    for ci in c:
        ci[0] = n
    return n

cnt = 0
while len(B):
    x, y = B.pop()
    wx = find(x)
    wy = find(y)
    if wx is wy:
        pt.append(0)
    else:
        pt.append(wx[1] * wy[1])
        wx[1] += wy[1]
        wy[0] = wx

    #print(G)

cnt = 0
for _ in range(M):
    cnt += pt.pop()
    print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Sep 15 01:01:58 2020

@author: liang
"""
#ゼロパディング＋インデックス
#str(1).zfill(6) + str(a.index(2) + 1).zfill(6)

N, M = map(int, input().split())
d = [list() for _ in range(N)]
P = list()

#insert O(M)
for i in range(M):
    p, y = map(int,input().split())
    d[p-1].append(y)
    P.append((p,y))

#year sort O(N log N)
for i in range(N):
    d[i].sort()

#search O(M)
for i in range(M):
    p, y = P[i]
    ans = str(p).zfill(6)+str(d[p-1].index(y)+1).zfill(6)
    print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Sep 15 01:01:58 2020

@author: liang
"""
#ゼロパディング＋インデックス
#str(1).zfill(6) + str(a.index(2) + 1).zfill(6)
#index(x) が重い => indexを使わなくて良いようにする

N, M = map(int, input().split())
#d = [list() for _ in range(N)]
dic = dict()
dic2 = dict()
P = list()

#insert O(M)
for i in range(M):
    p, y = map(int,input().split())
    #d[p-1].append(y)
    if p not in dic.keys():
        dic[p] = [y]
    else:
        dic[p].append(y)
    P.append((p,y))

#year sort O(N log N) => 重い　dict使用
#for i in range(N):
#    d[i].sort()
for key in dic.keys():
    dic[key].sort()

for key in dic.keys():
    for i in range(len(dic[key])):
        dic2[dic[key][i]] = i+1
#search O(M)***
for i in range(M):
    p, y = P[i]
    #ans = str(p).zfill(6)+str(d[p-1].index(y)+1).zfill(6)
    # zfill 重い？
    ans = ''
    ans += '0'*( 6 - len(str(p))) + str(p)
    #t = dic[p].index(y)+1
    t = dic2[y]
    ans += '0'*( 6 - len(str(t))) + str(t)
    print(ans)