Buggy python submission (verdict: Time Limit Exceeded):
# import sys
 
# N:県, M:市
N, M = list(map(int, input().split()))

A = {}
# {ken: [(city_no, city_year)],...}

res = [None] * M

for i in range(M):
  k, y = list(map(int, input().split()))
  if k in A.keys():
    A[k].append((i, y))
  else:
    A[k] = [(i, y)]

# print(A)
# A: {県番号: {市1の年:市1のindex, 市2の年:市2のindex}}

for k, v in A.items():
  # sort by year
  c_list = sorted(v, key=lambda x: x[1])
  counter = 1
  for c in c_list:
    res[c[0]] = (k, counter)
    counter += 1

for x in res:
  print("{:0>6}{:0>6}".format(x[0], x[1]))


Fixed submission:
# import sys
 
# N:県, M:市
N, M = list(map(int, input().split()))

A = {}
# {ken: [(city_no, city_year)],...}

res = [None] * M

for i in range(M):
  k, y = list(map(int, input().split()))
  if k in A.keys():
    A[k].append((i, y))
  else:
    A[k] = [(i, y)]

# print(A)
# A: {県番号: {市1の年:市1のindex, 市2の年:市2のindex}}

for k, v in A.items():
  # sort by year
  c_list = sorted(v, key=lambda x: x[1])
  counter = 1
  for c in c_list:
    res[c[0]] = (k, counter)
    counter += 1

for x in res:
  print("{:0>6}{:0>6}".format(x[0], x[1]))

Buggy python submission (verdict: Time Limit Exceeded):
# import sys
# import collections
# import numpy as np

# N:県, M:市
N, M = list(map(int, input().split()))
# od = collections.OrderedDict()

L = []
A = {}
B = {}

for i in range(M):
  x = tuple(map(int, input().split()))
  L.append(x)
  k = x[0]
  if k in A.keys():
    A[k].append(x[1])
  else:
    A[k] = [x[1]]  

#print(A)
# A: {県番号: {市1の年:市1のindex, 市2の年:市2のindex}}
 
#c = collections.OrderedDict([('Kuroda', 18), ('Ichiroh', 51), ('Matsui', 55)])
#print(c['Kuroda'])
 
# 県番号でソート
for k in A.keys():
  # keyでソート
  B[k] = (sorted(A[k]))

#print(B)

for x in L:
  # print(B[x[0]])
  # print(x[1])
  num = (B[x[0]].index(x[1])) + 1
  print("{:0>6}{:0>6}".format(x[0], num))
 
 

Fixed submission:
# import sys
 
# N:県, M:市
N, M = list(map(int, input().split()))

A = {}
# {ken: [(city_no, city_year)],...}

res = [None] * M

for i in range(M):
  k, y = list(map(int, input().split()))
  if k in A.keys():
    A[k].append((i, y))
  else:
    A[k] = [(i, y)]

# print(A)
# A: {県番号: {市1の年:市1のindex, 市2の年:市2のindex}}

for k, v in A.items():
  # sort by year
  c_list = sorted(v, key=lambda x: x[1])
  counter = 1
  for c in c_list:
    res[c[0]] = (k, counter)
    counter += 1

for x in res:
  print("{:0>6}{:0>6}".format(x[0], x[1]))

Buggy python submission (verdict: Time Limit Exceeded):
# import sys
# import collections
# import numpy as np

# N:県, M:市
N, M = list(map(int, input().split()))
# od = collections.OrderedDict()
L = [tuple(map(int, input().split())) for _ in range(M)]
A = {}
B = {}

for i in range(M):
  x = L[i]
  k = x[0]
  if k in A.keys():
    # print(A[k])
    # print(x)
    A[k].append(x[1])
  else:
    A[k] = [x[1]]

#print(A)
# A: {県番号: {市1の年:市1のindex, 市2の年:市2のindex}}

#c = collections.OrderedDict([('Kuroda', 18), ('Ichiroh', 51), ('Matsui', 55)])
#print(c['Kuroda'])

# 県番号でソート
for k in A.keys():
  # keyでソート
  B[k] = (sorted(A[k]))

#print(B)

for x in L:
  # print(B[x[0]])
  # print(x[1])
  num = (B[x[0]].index(x[1])) + 1
  print("{:0>6}{:0>6}".format(x[0], num))




Fixed submission:
# import sys
 
# N:県, M:市
N, M = list(map(int, input().split()))

A = {}
# {ken: [(city_no, city_year)],...}

res = [None] * M

for i in range(M):
  k, y = list(map(int, input().split()))
  if k in A.keys():
    A[k].append((i, y))
  else:
    A[k] = [(i, y)]

# print(A)
# A: {県番号: {市1の年:市1のindex, 市2の年:市2のindex}}

for k, v in A.items():
  # sort by year
  c_list = sorted(v, key=lambda x: x[1])
  counter = 1
  for c in c_list:
    res[c[0]] = (k, counter)
    counter += 1

for x in res:
  print("{:0>6}{:0>6}".format(x[0], x[1]))