Connect cities

import queue

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

heads = []
visited = set()
not_visited = set([i for i in range(1, n + 1)])
q = queue.Queue()


def dfs() -> None:
    while not q.empty():
        node = q.get()
        if node in visited:
            continue
        visited.add(node)
        not_visited.remove(node)
        for s in adj[node]:
            q.put(s)


while len(visited) < n:
    h = not_visited.pop()
    not_visited.add(h)
    heads.append(h)
    q.put(h)
    dfs()

print(len(heads) - 1)
for i in range(len(heads) - 1):
    print(f"{heads[i]} {heads[i + 1]}")

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