Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int,input().split())
all_city = [list(map(int,input().split())) for i in range(M)]

city = {}
for i in all_city:
    if i[0] in city:
        city[i[0]].append(i[1])
    else:
        city[i[0]] = [i[1]]

for i,k in city.items():
    city[i] = sorted(k)

def change_Prefecture_code(prefecture):
    return str(prefecture).zfill(6)

def change_birth_code(birth_num):
    return str(birth_num).zfill(6)


for i in all_city:
    city_num = i[0]
    ind = city[city_num].index(i[1]) + 1
    print(change_Prefecture_code(city_num) + change_birth_code(ind))

Fixed submission:
N, M = map(int,input().split())
all_city = [list(map(int,input().split())) for i in range(M)]
 
city = {}
for i in all_city:
    if i[0] in city:
        city[i[0]].append(i[1])
    else:
        city[i[0]] = [i[1]]
 
under6 = {}
for i,k in city.items():
    city[i] = sorted(k)
    for j in range(len(city[i])):
        under6[city[i][j]] = j + 1

def change_Prefecture_code(prefecture):
    return str(prefecture).zfill(6)
 
def change_birth_code(birth_num):
    return str(birth_num).zfill(6)
 
for i in all_city:
    print(change_Prefecture_code(i[0]) + change_birth_code(under6[i[1]]))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int,input().split())
all_city = [list(map(int,input().split())) for i in range(M)]

city = {}
for i in all_city:
    if i[0] in city:
        city[i[0]].append(i[1])
    else:
        city[i[0]] = [i[1]]


for i,k in city.items():
    city[i] = sorted(k)

def change_Prefecture_code(prefecture):
    return str(prefecture).zfill(6)

def change_birth_code(birth_num):
    return str(birth_num).zfill(6)

for i in all_city:
    print(change_Prefecture_code(i[0]) + change_birth_code(city[i[0]].index(i[1]) + 1))

Fixed submission:
N, M = map(int,input().split())
all_city = [list(map(int,input().split())) for i in range(M)]
 
city = {}
for i in all_city:
    if i[0] in city:
        city[i[0]].append(i[1])
    else:
        city[i[0]] = [i[1]]
 
under6 = {}
for i,k in city.items():
    city[i] = sorted(k)
    for j in range(len(city[i])):
        under6[city[i][j]] = j + 1

def change_Prefecture_code(prefecture):
    return str(prefecture).zfill(6)
 
def change_birth_code(birth_num):
    return str(birth_num).zfill(6)
 
for i in all_city:
    print(change_Prefecture_code(i[0]) + change_birth_code(under6[i[1]]))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int,input().split())
all_city = [list(map(int,input().split())) for i in range(M)]

city = {}
for i in all_city:
    if i[0] in city:
        city[i[0]].append(i[1])
    else:
        city[i[0]] = [i[1]]

for i,k in city.items():
    city[i] = sorted(k)

def change_Prefecture_code(prefecture):
    return str(prefecture).zfill(6)

def change_birth_code(birth_num):
    return str(birth_num).zfill(6)

for i in all_city:
    print(change_Prefecture_code(i[0]) + change_birth_code(city[i[0]].index(i[1]) + 1))

Fixed submission:
N, M = map(int,input().split())
all_city = [list(map(int,input().split())) for i in range(M)]
 
city = {}
for i in all_city:
    if i[0] in city:
        city[i[0]].append(i[1])
    else:
        city[i[0]] = [i[1]]
 
under6 = {}
for i,k in city.items():
    city[i] = sorted(k)
    for j in range(len(city[i])):
        under6[city[i][j]] = j + 1

def change_Prefecture_code(prefecture):
    return str(prefecture).zfill(6)
 
def change_birth_code(birth_num):
    return str(birth_num).zfill(6)
 
for i in all_city:
    print(change_Prefecture_code(i[0]) + change_birth_code(under6[i[1]]))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int,input().split())
all_city = [list(map(int,input().split())) for i in range(M)]

city = {}
for i in all_city:
    if i[0] in city:
        city[i[0]].append(i[1])
    else:
        city[i[0]] = [i[1]]

for i,k in city.items():
    city[i] = sorted(k)

def change_Prefecture_code(prefecture):
    return str(prefecture).zfill(6)

def change_birth_code(birth_num):
    return str(birth_num).zfill(6)

for i in all_city:
    print(change_Prefecture_code(i[0]) + change_birth_code(city[i[0]].index(i[1]) + 1))

Fixed submission:
N, M = map(int,input().split())
all_city = [list(map(int,input().split())) for i in range(M)]
 
city = {}
for i in all_city:
    if i[0] in city:
        city[i[0]].append(i[1])
    else:
        city[i[0]] = [i[1]]
 
under6 = {}
for i,k in city.items():
    city[i] = sorted(k)
    for j in range(len(city[i])):
        under6[city[i][j]] = j + 1

def change_Prefecture_code(prefecture):
    return str(prefecture).zfill(6)
 
def change_birth_code(birth_num):
    return str(birth_num).zfill(6)
 
for i in all_city:
    print(change_Prefecture_code(i[0]) + change_birth_code(under6[i[1]]))