Connect cities

def findRoadsToBuild(cityMappingDict, n):
  graphs = []
  visited = set()
 
  for city in range(1, n + 1):
    if city not in visited:
      graph = []
      dfs(city, cityMappingDict, visited, graph)
      graphs.append(graph)
 
  roadsToBuildList = []
  for i in range(1, len(graphs)):
    roadsToBuildList.append((graphs[i - 1][0], graphs[i][0]))
 
  return roadsToBuildList
 
def dfs(city, cityMappingDict, visited, graph):
  stack = [city]
  visited.add(city)
 
  while stack:
    currCity = stack.pop()
    graph.append(currCity)
 
    for neighbour in cityMappingDict[currCity]:
      if neighbour not in visited:
        visited.add(neighbour)
        stack.append(neighbour)
 
# first line, n (number of cities) and m (number of roads)
import sys
 
input = sys.stdin.readline()
numCitiesNumRoadsInput = input.split()
# print("numCitiesNumRoadsInput:", numCitiesNumRoadsInput)
n = int(numCitiesNumRoadsInput[0])
m = int(numCitiesNumRoadsInput[1])
 
if n == 1:
  sys.stdout.write("0\n")
elif n == 2 and m == 1:
  sys.stdout.write("0\n")
else:
  # initialise dict to act as an adjacency list
  cityMappingDict = dict()
 
  # subsequent lines, roads connecting cities
  for i in range(m):
    input = sys.stdin.readline()
    cityRoadConnectionString = input.split()
    leftCity = int(cityRoadConnectionString[0])
    rightCity = int(cityRoadConnectionString[1])
 
    if leftCity not in cityMappingDict:
      cityMappingDict[leftCity] = []
    if rightCity not in cityMappingDict:
      cityMappingDict[rightCity] = []
 
    cityMappingDict[leftCity].append(rightCity)
    cityMappingDict[rightCity].append(leftCity)
 
  # fill in missing cities who don't have any roads
  for i in range(1, n + 1):
    if i not in cityMappingDict:
      cityMappingDict[i] = []
 
  # print(cityMappingDict)
 
  newRoads = findRoadsToBuild(cityMappingDict, n)
 
  sys.stdout.write(f"{len(newRoads)}\n")
 
  for newRoad in newRoads:
    sys.stdout.write(f"{newRoad[0]} {newRoad[1]}\n")
 

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