Connect cities

n, m = input().split()
n, m = int(n), int(m)
group_index_of_cities = list(range(1,n+1))
cities_for_index = {k:{k} for k in range(1,n+1)}
for route in range(m):
    a, b = input().split()
    a, b = int(a), int(b)
    if group_index_of_cities[a-1]!=group_index_of_cities[b-1]:
        set_to_change = cities_for_index.pop(group_index_of_cities[b-1])
        for city in set_to_change:
            group_index_of_cities[city-1] = group_index_of_cities[a-1]
        cities_for_index[group_index_of_cities[a-1]] |= set_to_change
# print(group_index_of_cities)
# print(cities_for_index)


count_bridges = 0
bridges_list = []
for city in range(1,n):
    if group_index_of_cities[city] != group_index_of_cities[city-1]:
        # print("Bridging cities", city, "(group", group_index_of_cities[city-1],") and", city+1,"(group", group_index_of_cities[city],")")
        count_bridges+=1
        bridges_list.append((city, city+1))
        set_to_bridge = cities_for_index.pop(group_index_of_cities[city])
        for city_to_move in set_to_bridge:
            group_index_of_cities[city_to_move-1] = group_index_of_cities[city]
        cities_for_index[group_index_of_cities[city-1]] |= set_to_bridge

print(count_bridges)
for br in bridges_list:
    print(br[0], br[1])

Test 1

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 27, in <module>
    cities_for_index[group_index_of_cities[city-1]] |= set_to_bridge
    ~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
KeyError: 1

Test 2

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 27, in <module>
    cities_for_index[group_index_of_cities[city-1]] |= set_to_bridge
    ~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
KeyError: 4

Test 3

Verdict: ACCEPTED

Test 4

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 27, in <module>
    cities_for_index[group_index_of_cities[city-1]] |= set_to_bridge
    ~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
KeyError: 6

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 27, in <module>
    cities_for_index[group_index_of_cities[city-1]] |= set_to_bridge
    ~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
KeyError: 3

Test 12

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 27, in <module>
    cities_for_index[group_index_of_cities[city-1]] |= set_to_bridge
    ~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
KeyError: 1