Connect cities

import sys

def solve():
    # Read all input from standard input at once
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    m = int(input_data[1])
    
    # Build the adjacency list
    adj = [[] for _ in range(n + 1)]
    
    # input_data[0] is n, input_data[1] is m. 
    # Edges start from index 2.
    idx = 2
    for _ in range(m):
        u = int(input_data[idx])
        v = int(input_data[idx+1])
        adj[u].append(v)
        adj[v].append(u)
        idx += 2
        
    visited = [False] * (n + 1)
    representatives = []
    
    # Find all connected components
    for i in range(1, n + 1):
        if not visited[i]:
            # Save node 'i' as the representative of a new component
            representatives.append(i)
            
            # Iterative DFS using a stack
            stack = [i]
            visited[i] = True
            
            while stack:
                node = stack.pop()
                for neighbor in adj[node]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        stack.append(neighbor)
                        
    # The number of new roads is components - 1
    k = len(representatives) - 1
    
    # Prepare the output efficiently
    out = [str(k)]
    for i in range(1, len(representatives)):
        out.append(f"{representatives[i-1]} {representatives[i]}")
        
    # Print all at once
    sys.stdout.write('\n'.join(out) + '\n')

if __name__ == '__main__':
    solve()

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