Connect cities

n, m = list(map(int, input().split()))

roads = []

for _ in range(m):
    a, b = list(map(int, input().split()))
    roads.append((a, b))

graph = {}

for i in range(1, n + 1):
    graph[i] = []

for road in roads:
    a, b = road
    graph[a].append(b)
    graph[b].append(a)

visited = set()
components =  []

for node in range(1, n + 1):
    if node in visited:
        continue
    visited.add(node)
    component = []
    queue = list()
    queue.append(node)

    while len(queue) > 0:
        current_node = queue.pop()
        component.append(current_node)
        for adj_node in graph[current_node]:
            if not adj_node in visited:
                visited.add(adj_node)
                queue.append(adj_node)

    components.append(component)

n_components = len(components)

print(n_components - 1)

i = 0

while i < n_components - 1:
    edge1 = components[i][0]
    edge2 = components[i + 1][0]
    print(f"{edge1} {edge2}")
    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