Connect cities

import sys
sys.setrecursionlimit(200000)

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
        
    visited = [False] * (n + 1)
    
    def dfs(node):
        visited[node] = True
        for neighbor in adj[node]:
            if not visited[neighbor]:
                dfs(neighbor)
                
    reps = []
    for i in range(1, n + 1):
        if not visited[i]:
            reps.append(i)
            dfs(i)
            
    print(len(reps) - 1)
    for i in range(len(reps) - 1):
        print(f"{reps[i]} {reps[i+1]}")

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