Connect cities

#!/usr/bin/env python3

'''Connect Cities'''

from collections import deque

def main():
    '''Main'''
    n,m = [int(x) for x in input().split()]
    graph = [[0 for _ in range(n)] for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) for x in input().split()]
        graph[a-1][b-1] = 1
        graph[b-1][a-1] = 1
    nb_roads = 0
    cities_to_connect = []
    visited = [False for _ in range(n)]
    cities_to_visit = deque([0])

    while False in visited:
        if len(cities_to_visit) > 0:
            actual_node = cities_to_visit.popleft()
            if visited[actual_node]:
                continue
            visited[actual_node] = True
            for ind, road in enumerate(graph[actual_node]):
                if road:
                    cities_to_visit.append(ind)
        else:
            nb_roads += 1
            city_no_connect = visited.index(False)
            city_connected = visited.index(True)
            cities_to_connect.append((city_no_connect+1, city_connected+1))
            graph[city_no_connect][city_connected] = 1
            graph[city_connected][city_no_connect] = 1
            cities_to_visit.append(city_no_connect)

    print(nb_roads)
    for elt in cities_to_connect:
        print(str(elt[0]) + ' ' + str(elt[1]))

main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: RUNTIME ERROR

Test 7

Verdict: RUNTIME ERROR

Test 8

Verdict: RUNTIME ERROR

Test 9

Verdict: RUNTIME ERROR

Test 10

Verdict: RUNTIME ERROR

Test 11

Verdict: RUNTIME ERROR

Test 12

Verdict: ACCEPTED