Connect cities

import sys

def find(a, parent):
    while parent[a] != a:
        parent[a] = parent[parent[a]]
        a = parent[a]
    return a

def union(a, b, parent, size):
    ra, rb = find(a, parent), find(b, parent)
    if ra == rb:
        return
    if size[ra] < size[rb]:
        ra, rb = rb, ra
    parent[rb] = ra
    size[ra] += size[rb]

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    n = next(it); m = next(it)

    parent = list(range(n + 1))
    size = [1] * (n + 1)

    for _ in range(m):
        a = next(it); b = next(it)
        union(a, b, parent, size)
    rep_for_root = {}
    for city in range(1, n + 1):
        root = find(city, parent)
        if root not in rep_for_root:
            rep_for_root[root] = city

    reps = list(rep_for_root.values())
    k = len(reps) - 1
    out_lines = [str(k)]
    for i in range(1, len(reps)):
        out_lines.append(f"{reps[0]} {reps[i]}")

    sys.stdout.write("\n".join(out_lines))

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