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]:
        if len(cities_for_index[group_index_of_cities[a-1]])<len(cities_for_index[group_index_of_cities[b-1]]):
            a,b = b,a
        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],")")
        # if len(cities_for_index[group_index_of_cities[a-1]])<len(group_index_of_cities[b-1]):
        #     a,b = b,a
        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-1]
        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: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED