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)

  # print("Graphs:", graphs)

  roadsToBuildList = []
  for i in range(1, len(graphs)):
    if graphs[i - 1] and graphs[i]:
      roadsToBuildList.append((graphs[i - 1][0], graphs[i][0]))

  return roadsToBuildList

def dfs(city, cityMappingDict, visited, graph):
  visited.add(city)
  graph.append(city)
  for neighbour in cityMappingDict.get(city, []):
    if neighbour not in visited:
      dfs(neighbour, cityMappingDict, visited, graph)


# first line, n (number of cities) and m (number of roads)
numCitiesNumRoadsInput = input().split()
n = int(numCitiesNumRoadsInput[0])
m = int(numCitiesNumRoadsInput[1])

if n == 1:
  print(0)
elif n == 2 and m == 1:
  print(0)
else:
  # initialise dict to act as an adjacency list
  cityMappingDict = dict()

  # subsequent lines, roads connecting cities
  for i in range(m):
    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)

    # leftCityList = cityMappingDict.get(leftCity, [])
    # leftCityList.append(rightCity)
    # cityMappingDict[leftCity] = leftCityList

    # rightCityList = cityMappingDict.get(rightCity, [])
    # rightCityList.append(leftCity)
    # cityMappingDict[rightCity] = rightCityList

  print(cityMappingDict)

  newRoads = findRoadsToBuild(cityMappingDict, n)

  print(len(newRoads))

  for newRoad in newRoads:
    print(newRoad[0], newRoad[1])

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: ACCEPTED

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

Test 6

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 65, in <module>
    n...

Test 7

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 65, in <module>
    n...

Test 8

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 65, in <module>
    n...

Test 9

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 65, in <module>
    n...

Test 10

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 65, in <module>
    n...

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER