Connect cities

import sys
sys.setrecursionlimit(10**6)
 
n, m = map(int, input().split())
 
g = {}
for i in range(1, n + 1):
    g[i] = []
 
# Build the graph
for i in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
 
visited = []
for i in range(n+1):
    visited.append(False)
 
# DFS function
def dfs(node, visited, temp):
    visited[node] = True
    temp.append(node)
    for neighbor in g[node]:
        if not visited[neighbor]:
            dfs(neighbor, visited, temp)
 
connected_components = []
 
for i in range(1, n + 1):
    if not visited[i]:
        temp = []
        dfs(i, visited, temp)
        connected_components.append(temp)
 
 
k = len(connected_components) - 1
print(k)
 
if k > 0:
    for i in range(k):
        print(str(connected_components[i][0]) + " " + str(connected_components[i + 1][0]))

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