Connect cities

# Dictionary for speed.
builtRoads = {}

## Get adjecent cities of a city.
def getAdjecent(city: int) -> list[int]:
    return builtRoads.get(city, [])
 
def getGroupings(cities: int) -> list[list[int]]:
    ## Store groupings
    cityGroupings = []
 
    # Store unchecked cities as a set for speed.
    uncheckedCities = set(range(1, cities + 1))
 
    # While we have cities to check.
    while(len(uncheckedCities) != 0):
        # Current
        current = next(iter(uncheckedCities))

        visited = []
        visitedSet = set()

        yetToVisit = getAdjecent(current)
        yetToVisitSet = set(yetToVisit)
 
        # If this city is alone, just add it to list.
        if(len(yetToVisit) == 0):
            visited.append(current)
            visitedSet.add(current)
 
        while(len(yetToVisit) != 0):
 
            # Append current city and change it.
            visited.append(current)
            visitedSet.add(current)

            current = yetToVisit[0]
 
            # remove current one.
            yetToVisit.pop(0)
            yetToVisitSet.discard(current)
 
            # Add new adjecent cities that we have not been to.
            for n in getAdjecent(current):
                if n not in visitedSet and n not in yetToVisitSet:
                    yetToVisit.append(n)
                    yetToVisitSet.add(n)
 
        # Last one
        if current not in visitedSet:
            visited.append(current)
            visitedSet.add(current)
        
        cityGroupings.append(visited)
 
        # Remove all of these cities from unchecked.
        uncheckedCities.difference_update(visitedSet)
 
    return cityGroupings
 
 
 
# Read input
read = input().split(" ")
cityCount = int(read[0])
roadCount = int(read[1])
 
# Read list of roads
for i in range(0, roadCount):
    a, b = map(int, input().split(" "))

    # Ini dict for speed.
    if a not in builtRoads: builtRoads[a] = []
    builtRoads[a].append(b)
    if b not in builtRoads: builtRoads[b] = []
    builtRoads[b].append(a)
 
# Figure out groupings.
# Array of cities grouped on their connectivity.
groupedCityArray = getGroupings(cityCount)
 
# Array of needed roads
neededRoadArray = []
 
# Add a new path that connects groups. Use first node in group.
## Basically just create a circle, where the last two are not connected.
for i in range(0, len(groupedCityArray) - 1):
    neededRoadArray.append([groupedCityArray[i][0], groupedCityArray[i + 1][0]])
 
# Output
print(len(neededRoadArray))
for i in neededRoadArray:
    print(str(i[0])+" "+str(i[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: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED