Connect cities

cities_num, roads_num = [int(x) for x in input().split()]
visited = [False for _ in range(cities_num+1)]
adj = [[]for _ in range(cities_num+1)] #5 empty lists



def addAdj(adjList, city, connected_city):
    adjList[city].append(connected_city)
    adjList[connected_city].append(city)

def dfs(node):
    stack = [node]
    visited[node] = True
    while stack:
        new_node = stack.pop()
        for x in adj[new_node]:
            if not visited[x]:
                visited[x] = True
                stack.append(x)

def main():
    lonely_nodes = []

    for i in range(roads_num):
        city, connected_city = [int(x) for x in input().split()]
        addAdj(adj, city, connected_city)
    
    lonely_nodes.append(1)
    dfs(1)
    
    for j in range(1,cities_num+1):
        if not visited[j]:
            lonely_nodes.append(j)
            dfs(j)
    #amount of roads needed to connect all unconnected groups is groups-1
    print(len(lonely_nodes)-1)
    for k in range(1,len(lonely_nodes)):
        print(lonely_nodes[k-1],lonely_nodes[k])

if __name__ == "__main__":
    main()

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