Buggy python submission (verdict: Time Limit Exceeded):
number_of_prefecture, number_of_cities = [int(x) for x in input().split(' ')]

city_list = []

import bisect
import collections
city_dict = collections.defaultdict(list)

for i in range (number_of_cities):
    prefecture_id, year_of_establishment = [int(x) for x in input().split(' ')]
    index = bisect.bisect_left(city_dict[prefecture_id], year_of_establishment)
    city_dict[prefecture_id].insert(index, year_of_establishment)
    city_list.append([prefecture_id, year_of_establishment])

for j in city_list:
    prefecture = j[0]
    year = j[1]
    city_number = bisect.bisect(city_dict[prefecture],year)
    front_string = '0'*(6 - len(str(prefecture))) + str(prefecture)
    back_string = '0'*(6 - len(str(city_number))) + str(city_number)
    print(front_string+back_string)


Fixed submission:
number_of_prefecture, number_of_cities = [int(x) for x in input().split(' ')]

city_list = []

import bisect
import collections
city_dict = collections.defaultdict(list)

for i in range (number_of_cities):
    prefecture_id, year_of_establishment = [int(x) for x in input().split(' ')]
    city_dict[prefecture_id].append(year_of_establishment)
    city_list.append([prefecture_id, year_of_establishment])

for prefecture in city_dict:
    city_dict[prefecture].sort()

for j in city_list:
    prefecture = j[0]
    year = j[1]
    city_number = bisect.bisect(city_dict[prefecture],year)
    front_string = '0'*(6 - len(str(prefecture))) + str(prefecture)
    back_string = '0'*(6 - len(str(city_number))) + str(city_number)
    print(front_string+back_string)

Buggy python submission (verdict: Time Limit Exceeded):
number_of_prefecture, number_of_cities = [int(x) for x in input().split(' ')]

city_list = []

import bisect
import collections
city_dict = collections.defaultdict(list)

for i in range (number_of_cities):
    prefecture_id, year_of_establishment = [int(x) for x in input().split(' ')]
    index = 0
    for k in city_dict[prefecture_id]:
        if year_of_establishment > k:
            index += 1
        else:
            break
    city_dict[prefecture_id].insert(index, year_of_establishment)
    city_list.append([prefecture_id, year_of_establishment])

for j in city_list:
    prefecture = j[0]
    year = j[1]
    city_number = bisect.bisect(city_dict[prefecture],year)
    front_string = '0'*(6 - len(str(prefecture))) + str(prefecture)
    back_string = '0'*(6 - len(str(city_number))) + str(city_number)
    print(front_string+back_string)


Fixed submission:
number_of_prefecture, number_of_cities = [int(x) for x in input().split(' ')]

city_list = []

import bisect
import collections
city_dict = collections.defaultdict(list)

for i in range (number_of_cities):
    prefecture_id, year_of_establishment = [int(x) for x in input().split(' ')]
    city_dict[prefecture_id].append(year_of_establishment)
    city_list.append([prefecture_id, year_of_establishment])

for prefecture in city_dict:
    city_dict[prefecture].sort()

for j in city_list:
    prefecture = j[0]
    year = j[1]
    city_number = bisect.bisect(city_dict[prefecture],year)
    front_string = '0'*(6 - len(str(prefecture))) + str(prefecture)
    back_string = '0'*(6 - len(str(city_number))) + str(city_number)
    print(front_string+back_string)

Buggy python submission (verdict: Time Limit Exceeded):
number_of_prefecture, number_of_cities = [int(x) for x in input().split(' ')]

city_list = []

import collections
city_dict = collections.defaultdict(list)

for i in range (number_of_cities):
    prefecture_id, year_of_establishment = [int(x) for x in input().split(' ')]
    index = 0
    for k in city_dict[prefecture_id]:
        if year_of_establishment > k:
            index += 1
        else:
            break
    city_dict[prefecture_id].insert(index, year_of_establishment)
    city_list.append([prefecture_id, year_of_establishment])

for j in city_list:
    prefecture = j[0]
    year = j[1]
    city_number = city_dict[prefecture].index(year) + 1
    front_string = '0'*(6 - len(str(prefecture))) + str(prefecture)
    back_string = '0'*(6 - len(str(city_number))) + str(city_number)
    print(front_string+back_string)


Fixed submission:
number_of_prefecture, number_of_cities = [int(x) for x in input().split(' ')]

city_list = []

import bisect
import collections
city_dict = collections.defaultdict(list)

for i in range (number_of_cities):
    prefecture_id, year_of_establishment = [int(x) for x in input().split(' ')]
    city_dict[prefecture_id].append(year_of_establishment)
    city_list.append([prefecture_id, year_of_establishment])

for prefecture in city_dict:
    city_dict[prefecture].sort()

for j in city_list:
    prefecture = j[0]
    year = j[1]
    city_number = bisect.bisect(city_dict[prefecture],year)
    front_string = '0'*(6 - len(str(prefecture))) + str(prefecture)
    back_string = '0'*(6 - len(str(city_number))) + str(city_number)
    print(front_string+back_string)

Buggy python submission (verdict: Time Limit Exceeded):
number_of_prefecture, number_of_cities = [int(x) for x in input().split(' ')]

city_list = []

import collections
city_dict = collections.defaultdict(list)

for i in range (number_of_cities):
    prefecture_id, year_of_establishment = [int(x) for x in input().split(' ')]
    city_dict[prefecture_id].append(year_of_establishment)
    city_list.append([prefecture_id, year_of_establishment])

for prefecture in city_dict:
    city_dict[prefecture].sort()

# print(city_dict)
# print(city_list)

for j in city_list:
    prefecture = j[0]
    year = j[1]
    city_number = city_dict[prefecture].index(year) + 1
    front_string = '0'*(6 - len(str(prefecture))) + str(prefecture)
    back_string = '0'*(6 - len(str(city_number))) + str(city_number)
    print(front_string+back_string)


Fixed submission:
number_of_prefecture, number_of_cities = [int(x) for x in input().split(' ')]

city_list = []

import bisect
import collections
city_dict = collections.defaultdict(list)

for i in range (number_of_cities):
    prefecture_id, year_of_establishment = [int(x) for x in input().split(' ')]
    city_dict[prefecture_id].append(year_of_establishment)
    city_list.append([prefecture_id, year_of_establishment])

for prefecture in city_dict:
    city_dict[prefecture].sort()

for j in city_list:
    prefecture = j[0]
    year = j[1]
    city_number = bisect.bisect(city_dict[prefecture],year)
    front_string = '0'*(6 - len(str(prefecture))) + str(prefecture)
    back_string = '0'*(6 - len(str(city_number))) + str(city_number)
    print(front_string+back_string)