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