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

import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(N):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
count = 0
ans = []
bfs(0,G,queue,dist)
print("Yes")
for v in range(1,N): 
    for el in G[v]:
        if dist[el] + 1 == dist[v]:
            print(el+1)
            break

### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**9)
    from sys import stdin
    def input() : return stdin.readline().rstrip()
    N,M = map(int,input().split())
    dist = [-1] * N
    G = dict()
    for i in range(N):
        G[i] = []   
    for _ in range(M):
        a,b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    q = [0]
    pre = [0] * N
    dist[0] = 0
    while (q != []):
        v = q[0]
        q.remove(q[0])
        for vertex in G[v]:
            if dist[vertex] != -1:
                continue
            dist[vertex] = dist[v] + 1
            pre[vertex] = v
            q.append(vertex)
    print("Yes")
    for v in range(1,N): 
        print(pre[v]+1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def iter_bit(k, LIMIT):
    v = (1 << k) - 1

    while v < LIMIT:
        yield v
        x = v & -v
        y = v + x
        v = (v & ~y) // x >> 1 | y


def solve(n, cards):
    dp = [{} for _ in range(1 << n)]
    dp[-1][0] = 0
    LIMIT = 1 << n

    for d in range(n):
        for state in iter_bit(n - d, LIMIT):
            scores = dp[state]
            k = state
            curr = 0
            while k:
                b = k & -k
                i = b.bit_length() - 1
                num = cards[i][(d - i) % 2]
                next_dp = dp[state ^ b]
                for score, left_num in scores.items():
                    if left_num > num:
                        continue
                    ns = score + curr
                    if ns not in next_dp or next_dp[ns] > num:
                        next_dp[ns] = num
                k ^= b
                curr += 1

    if len(dp[0]) > 0:
        return min(dp[0].keys())
    else:
        return -1


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
cards = list(zip(aaa, bbb))
print(solve(n, cards))


### FIXED CODE ###

def iter_bit(k, LIMIT):
    v = (1 << k) - 1

    while v < LIMIT:
        yield v
        x = v & -v
        y = v + x
        v = (v & ~y) // x >> 1 | y


def solve(n, cards):
    dp = [{} for _ in range(1 << n)]
    dp[-1][0] = 0
    LIMIT = 1 << n

    for d in range(n):
        for state in iter_bit(n - d, LIMIT):
            scores = dp[state]
            k = state
            curr = 0
            while k:
                b = k & -k
                i = b.bit_length() - 1
                num = cards[i][(d - i) % 2]
                next_dp = dp[state ^ b]
                for left_num, score in scores.items():
                    if left_num > num:
                        continue
                    ns = score + curr
                    if num not in next_dp or next_dp[num] > ns:
                        next_dp[num] = ns
                k ^= b
                curr += 1

    if len(dp[0]) > 0:
        return min(dp[0].values())
    else:
        return -1


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
cards = list(zip(aaa, bbb))
print(solve(n, cards))
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

for i in range(N-1):
  print(max(A[:i]+A[i+1:]))
else:
  print(max(A[:N-1]))

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
 
A2 = sorted(A)[::-1]
for a in A:
  if a == A2[0]:
    print(A2[1])
  else:
    print(A2[0])
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline

N, M = [int(x) for x in input().strip().split()]
NL = [deque([]) for n in range(10 ** 5)]

IN = [0] * M
for m in range(M):
    IN[m] = tuple([int(x) for x in input().strip().split()]) 

for p, y in IN:
    NL[p-1].append(y)

for i, nl in enumerate(NL):
    NL[i] = sorted(nl)

for p, y in IN:
    print('{:06d}{:06d}'.format(p, NL[p-1].index(y) + 1))



### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline

N, M = [int(x) for x in input().strip().split()]
NL = [deque([]) for n in range(10 ** 5)]

IN = [0] * M
d = {}
for m in range(M):
    IN[m] = tuple([int(x) for x in input().strip().split()]) 

for p, y in IN:
    NL[p-1].append(y)

for p, nl in enumerate(NL, start=1):
    d[p] = {}
    for i, n in enumerate(sorted(nl), start=1):
        d[p][n] = i

for p, y in IN:
    print('{:06d}{:06d}'.format(p, d[p][y]))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
town=[1]
cnt=0
loop=0
index=0
while(cnt == index):
    town.append(a[town[-1]-1])
    cnt+=1
    index=town.index(town[-1])

town.pop(-1)
loop=cnt-index


if k<index:
    print(town[k])
else:
    k-=index
    k%=loop
    print(town[index+k])

### FIXED CODE ###

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

s=[]
ordn=[]
for i in range(n+1):
    ordn.append(-1)

v=1
while(ordn[v] == -1):
    ordn[v]=len(s)
    s.append(v)
    v=a[v-1]

c=len(s)-ordn[v]
l=ordn[v]

if k<l:
    print(s[k])
else:
    k -= l
    k%=c
    print(s[l+k])
### BUGGY CODE ###

import heapq

x, y, z, k = map(int, raw_input().split())
a = map(int, raw_input().split())
b = map(int, raw_input().split())
c = map(int, raw_input().split())

def diff(l):
    m = max(l)
    return sorted(m - v for v in l)[1:]

s = sum(map(max, [a, b, c]))
sa, sb, sc = map(diff, [a, b, c])
da, db, dc = [0], [0], [0]
q = [0]
while k > 0:
    while True:
        if len(sa) > 0 and (len(q) == 0 or q[0] >= sa[0]):
            for v in [sa[0] + bb + cc for bb in db for cc in dc]:
                heapq.heappush(q, v)
            da.append(sa[0])
            sa = sa[1:]
        elif len(sb) > 0 and (len(q) == 0 or q[0] >= sb[0]):
            for v in [sb[0] + aa + cc for aa in da for cc in dc]:
                heapq.heappush(q, v)
            db.append(sb[0])
            sb = sb[1:]
        elif len(sc) > 0 and (len(q) == 0 or q[0] >= sc[0]):
            for v in [sc[0] + aa + bb for aa in da for bb in db]:
                heapq.heappush(q, v)
            dc.append(sc[0])
            sc = sc[1:]
        else:
            break
    v = heapq.heappop(q)
    print s - v
    k -= 1


### FIXED CODE ###

import heapq

x, y, z, k = map(int, raw_input().split())
a = map(int, raw_input().split())
b = map(int, raw_input().split())
c = map(int, raw_input().split())

def diff(l):
    m = max(l)
    return sorted(m - v for v in l)[1:]

s = sum(map(max, [a, b, c]))
sa, sb, sc = map(diff, [a, b, c])
da, db, dc = [0], [0], [0]
q = [0]
while k > 0:
    while True:
        if len(sa) > 0 and (len(q) == 0 or q[0] > sa[0]):
            for v in [sa[0] + bb + cc for bb in db for cc in dc]:
                heapq.heappush(q, v)
            da.append(sa[0])
            sa = sa[1:]
        elif len(sb) > 0 and (len(q) == 0 or q[0] > sb[0]):
            for v in [sb[0] + aa + cc for aa in da for cc in dc]:
                heapq.heappush(q, v)
            db.append(sb[0])
            sb = sb[1:]
        elif len(sc) > 0 and (len(q) == 0 or q[0] > sc[0]):
            for v in [sc[0] + aa + bb for aa in da for bb in db]:
                heapq.heappush(q, v)
            dc.append(sc[0])
            sc = sc[1:]
        else:
            break
    v = heapq.heappop(q)
    print s - v
    k -= 1
### BUGGY CODE ###

import sys
n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
for i in range(m):
    if t[i] in d:
        d.remove(t[i])
    else:
        print('NO')
        sys.exit()
print('YES')

### FIXED CODE ###

import sys
from collections import Counter
n=int(input())
d=Counter(list(map(int,input().split())))
m=int(input())
t=Counter(list(map(int,input().split())))
k=list(t.keys())
for i in range(len(k)):
    if d[k[i]]<t[k[i]]:
        print('NO')
        sys.exit()
print('YES')
### BUGGY CODE ###

from bisect import bisect_right

n = int(input())

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

ans = 0

for x in a:
  i = bisect_right(b, x)
  for y in b[i:]:
    j = bisect_right(c, y)
    for z in c[j:]:
      ans += 1

print(ans)


### FIXED CODE ###

from bisect import bisect_right, bisect_left

n = int(input())

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

ans = 0
for x in b:
  ans += bisect_left(a, x) * (n - bisect_right(c, x))

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

s = str(input())
num = 0
m = 1
while m == 1:
    t = num
    for i in range(len(s)-1):
        if (s[i]=='0' and s[i+1]=='1') or (s[i]=='1' and s[i+1]=='0'):
            num += 2
            s = s[:i]+ s[i+2:]
            break
    if t == num:
        break
print(num)

### FIXED CODE ###

s = str(input())
x = s.count('0')
y = s.count('1')
print(min(x,y)*2)
### BUGGY CODE ###

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

ans1 = []
ans2 = []
while len(ans1) <= N:
    for i in range(A):
        ans1.append("b")
    for i in range(B):    
        ans1.append("r")
for i in range(N):
    if ans1[i] == "b":
        ans2.append(ans1[i])
print(len(ans2))

### FIXED CODE ###

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

C = N // (A + B)
D = N % (A + B)
ans = A * C

if D >= A:
    ans += A
else:
    ans += D
    
print(ans)
### BUGGY CODE ###

_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = []
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i,j))

a = [[True]*w + [False] for _ in range(h)]
a.append([False]*(w+1))

ans = 0
while True:
    ns = []
    for i, j in s:
        a[i][j] = False

        if a[i-1][j]:
            ns.append((i-1, j))
        if a[i+1][j]:
            ns.append((i+1, j))
        if a[i][j-1]:
            ns.append((i, j-1))
        if a[i][j+1]:
            ns.append((i, j+1))
        
    if not ns:
        break
    s = ns
    ans += 1
    
print(ans)

### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    m = []
    m.append([True] * (W + 2))
    for _ in range(H):
        m.append([True] + [c == '#' for c in input()] + [True])
    m.append([True] * (W + 2))
    queue = []
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if m[i][j]:
                queue.append((i, j))
    ans = -1
    while queue:
        ans += 1
        tmp = []
        for x, y in queue:
            if not m[x - 1][y]:
                m[x - 1][y] = True
                tmp.append((x - 1, y))
            if not m[x + 1][y]:
                m[x + 1][y] = True
                tmp.append((x + 1, y))
            if not m[x][y - 1]:
                m[x][y - 1] = True
                tmp.append((x, y - 1))
            if not m[x][y + 1]:
                m[x][y + 1] = True
                tmp.append((x, y + 1))
        queue = tmp
    print(ans)

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

#!/usr/bin/env python3
# Knapsack問題

# input
N,W = map(int, input().split())
w = []
v = []
for _ in range(N):
  a,b = map(int ,input().split())
  w.append(a)
  v.append(b)

# calc
dp = [[0 for _ in range(W+1)] for _ in range(N+2)]

for i in range(N):
    for j in range(W+1):
        if w[i] <= j:
            dp[i+1][j] = max(dp[i][j-w[i]]+v[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[N][W])


### FIXED CODE ###

# Knapsack問題

# input
N,W = map(int, input().split())
w = []
v = []
for _ in range(N):
    a,b = map(int ,input().split())
    w.append(a)
    v.append(b)

# calc
dp = [[0 for _ in range(W+1)] for _ in range(N+2)]

for i in range(N):
    for j in range(W+1):
        if w[i] <= j:
            dp[i+1][j] = max(dp[i][j-w[i]]+v[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[N][W])
### BUGGY CODE ###

x = int(input())

if x == 1:
    a = 1
    b = 0
else:
    p = 2
    while True:
        while True:
            if x % p == 0:
                q = int(x / p)
                break
            else:
                p += 1
        ap = p
        am = p
        bp = 0
        bm = 0
        for i in range(10000):
            if ap**4 + ap**3 * bp + ap**2 * bp**2 + ap * bp**3 + bp**4 == q:
                a = ap
                b = bp
                break
            elif am**4 + am**3 * bm + am**2 * bm**2 + am * bm**3 + bm**4 == q:
                a = am
                b = bm
                break
            ap += 1
            bp += 1
            am -= 1
            bm -= 1
        else:
            p += 1
            continue
        break

print('{} {}'.format(a, b))

### FIXED CODE ###

x = int(input())

if x == 1:
    a = 1
    b = 0
else:
    p = 1
    while True:
        while True:
            if x % p == 0:
                q = int(x / p)
                break
            else:
                p += 1
        ap = p
        am = p
        bp = 0
        bm = 0
        for i in range(200):
            if ap**4 + ap**3 * bp + ap**2 * bp**2 + ap * bp**3 + bp**4 == q:
                a = ap
                b = bp
                break
            elif am**4 + am**3 * bm + am**2 * bm**2 + am * bm**3 + bm**4 == q:
                a = am
                b = bm
                break
            ap += 1
            bp += 1
            am -= 1
            bm -= 1
        else:
            p += 1
            continue
        break

print('{} {}'.format(a, b))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

# dp[i] = 足場iに移動するのに必要な最小コスト
dp = [0 for _ in range(N)]

# DP配列更新
for i in range(1, N):
    # 最小コストで更新する
    max_k = min([i, K]) + 1
    dp[i] = min([dp[i - k] + abs(h[i] - h[i - k]) for k in range(1, max_k)])

print(dp[-1])


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import numpy as np

N, K = map(int, input().split())
h = list(map(int, input().split()))
# 高速化のためにnumpy使う
h = np.array(h)

# dp[i] = 足場iに移動するのに必要な最小コスト
dp = [0 for _ in range(N)]
# 高速化のためにnumpy使う
dp = np.array(dp)

# DP配列更新
"""
TLEだったやつ
for i in range(1, N):
    # 最小コストで更新する
    max_k = min([i, K]) + 1
    dp[i] = min([dp[i - k] + abs(h[i] - h[i - k]) for k in range(1, max_k)])
"""
for i in range(1, N):
    # 最小コストで更新する
    # K個まとめて移動コストを計算することで高速化
    # ただしマイナスからスタートするような値はスキップする
    s = max(0, i - K)
    dp[i] = np.min(dp[s:i] + np.abs(h[s:i] - h[i]))

print(dp[-1])
### BUGGY CODE ###

import collections

n = int(input())
dd = list(map(int, input().split()))
m = int(input())
tt = list(map(int, input().split()))
cd = collections.Counter(dd)
ct = collections.Counter(tt)

if m > n:
  print('NO')
  exit()
        

for t in tt: 
  if t in dd and ct[t] <= cd[t]:
    continue
  else:
    print('NO')
    exit()
print('YES')


### FIXED CODE ###

import collections
n = int(input())
d_list = list(map(int, input().split()))
m = int(input())
t_list = list(map(int, input().split()))

if m > n:
    print("NO")
    exit()

d_c = collections.Counter(d_list)
t_c = collections.Counter(t_list)

for i in t_c:
    if t_c[i] <= d_c[i]:
        continue
    else:
        print("NO")
        exit()

print("YES")
### BUGGY CODE ###

import math
from functools import reduce

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

k = int(input())
ans = 0

for i in range(1, k+1):
    for j in range(1,k+1):
        tmp = gcd(i,j)
        for m in range (1,k+1):
            ans += gcd(tmp,m)

print(ans)


### FIXED CODE ###

import math

k = int(input())
ans = 0

for i in range(1, k+1):
    for j in range(1,k+1):
        tmp = math.gcd(i,j)
        for m in range (1,k+1):
            ans += math.gcd(tmp,m)

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

H, W = map(int, input().split())
Map = []
for _ in range(H):
  List = list(input())
  Map.append(List)
points = [[0]*W for i in range(H)]
directions = [(1,0),(-1,0),(0,1),(0,-1)]
def countpoints(Map,i,j):
  ans = 1
  for direction in directions:
    p= i
    q = j
    while (0 <= p <= H-1) and (0 <= q <= W -1):
      p,q = p+direction[0],q+direction[1]
      if (p < 0 or H -1 < p) or (q < 0 or W-1 <q):
        break
      if Map[p][q] != '#':
        ans += 1
      else:
        break
  return ans
for i in range(H):
  for j in range(W):
    if Map[i][j] != '#':
      points[i][j] = countpoints(Map,i,j)
maxdata = []
for line in points:
  maxdata.append(max(line))
Answer = max(maxdata)
print(Answer)

### FIXED CODE ###

import numpy as np
H,W = map(int,input().split())
Map=[list(input()) for h in range(H)]
Map=[[1 if s=='.' else 0 for s in Map[h]] for h in range(H)]
Map=np.array(Map,dtype=int)
L=Map.copy()
R=Map.copy()
U=Map.copy()
D=Map.copy()
for w in range(1,W):
    L[:,w]=(L[:,w-1]+1)*Map[:,w]
    R[:,-(1+w)]=(R[:,-w]+1)*Map[:,-(1+w)]
for h in range(1,H):
    U[h,:]=(U[h-1,:]+1)*Map[h,:]
    D[-(1+h),:]=(D[-h,:]+1)*Map[-(1+h),:]
print((L+R+U+D).max()-3)
### BUGGY CODE ###

import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    n, m = map(int, input().split())

    ans = []

    for i in range(1, m // n + 1):
        if (m - i * n) % i == 0:
            ans.append(i)

    print(max(ans))


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 14"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """10 123"""
        output = """3"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """100000 1000000000"""
        output = """10000"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()


### FIXED CODE ###

import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    n, m = map(int, input().split())

    for i in reversed(range(1, m // n + 1)):
        if (m - i * n) % i == 0:
            print(i)
            return




# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 14"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """10 123"""
        output = """3"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """100000 1000000000"""
        output = """10000"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()
### BUGGY CODE ###

n=int(input())
arr=list(map(int,input().split()))
c=0
for i in range(1,n):
    m=0
    for j in range(i,0,-1):
       
        if arr[j-1]>m:
            m=arr[j-1]
        
    if arr[i]<m:
        c+=m-arr[i]
    
print(c)

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
c=0
for i in range(1,n):
    if arr[i]<arr[i-1]:
        c+=arr[i-1]-arr[i]
        arr[i]+=arr[i-1]-arr[i]
        
print(c)
### BUGGY CODE ###

import statistics
n = int(input())
x = [int(x) for x in input().split()]

#m = (n // 2) - 1
for i in range(n):
    l = x[:i] + x[i+1:]
#    l.sort()
    print(statistics.median(l))
    #print(l[m])

### FIXED CODE ###

n = int(input())
x = [int(x) for x in input().split()]

s = sorted(x)

for i in range(n):
    if x[i] <= s[n//2 - 1]:
        print(s[n//2])
    else:
        print(s[n//2 - 1])
### BUGGY CODE ###

N,M = map(int,input().split())
P = []

Indexs = []
Syuturyoku = []


for j in range(N):
	P.append([0])


for i in range(M):
	p,y = map(int,input().split())

	P[p-1].append(y)
	Indexs.append(y)
	Syuturyoku.append(("0","0"))

for i in range(len(P)):
	P[i].sort()
	# P[i] = list(map(str,P[i]))


for i in range(len(P)):
	if(len(P[i])>1):
		for j in range(len(P[i])-1):
			atai = P[i][j+1]
			si = i+1
			# si = str(si)
			x = j+1
			# x = str(x)
			# bangou = list(map(str,si))
			# bangou_len = int(len(bangou))
			# bangou_ushiro = list(map(str,x))
			# bangou_ushiro_len = int(len(bangou_ushiro))
			# if(len(bangou)<6):
			# 	for zero in range(6-bangou_len):
			# 		bangou.insert(0,'0')
			# if(len(bangou_ushiro)<6):
			# 	for zero in range(6-bangou_ushiro_len):
			# 		bangou_ushiro.insert(0,'0')

			# mojiretsu = ''
			# for k in bangou:
			# 	mojiretsu += k
			# mojiretsu2 = ''
			# for k2 in bangou_ushiro:
			# 	mojiretsu2 += k2

			a = Indexs.index(atai)
			Syuturyoku[a] = (si, x)
for i in range(M):
	print('{0:06}{1:06}'.format(Syuturyoku[i][0], Syuturyoku[i][1]))


### FIXED CODE ###

N,M = map(int,input().split())
P = []

Indexs = {}
Syuturyoku = []


for j in range(N):
	P.append([0])


for i in range(M):
	p,y = map(int,input().split())

	P[p-1].append(y)
	Indexs[y] = i
	Syuturyoku.append(0)

for i in range(len(P)):
	P[i].sort()
	# P[i] = list(map(str,P[i]))


for i in range(N):
	if (len(P[i]) > 1):
		for j in range(len(P[i])-1):
			atai = P[i][j+1]
			si = i+1
			# si = str(si)
			x = j+1
			# x = str(x)
			# bangou = list(map(str,si))
			# bangou_len = int(len(bangou))
			# bangou_ushiro = list(map(str,x))
			# bangou_ushiro_len = int(len(bangou_ushiro))
			# if(len(bangou)<6):
			# 	for zero in range(6-bangou_len):
			# 		bangou.insert(0,'0')
			# if(len(bangou_ushiro)<6):
			# 	for zero in range(6-bangou_ushiro_len):
			# 		bangou_ushiro.insert(0,'0')

			# mojiretsu = ''
			# for k in bangou:
			# 	mojiretsu += k
			# mojiretsu2 = ''
			# for k2 in bangou_ushiro:
			# 	mojiretsu2 += k2

			a = Indexs[atai]
			Syuturyoku[a] = (si, x)

for i in range(M):
	print('{0:06}{1:06}'.format(Syuturyoku[i][0], Syuturyoku[i][1]))