Connect cities

from collections import deque

def main():

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

    roads = []

    for _ in range(m):
        city1, city2 = map(int, input().split())
        roads.append((city1, city2))

    adjacency_list = {}

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

    for i in range(m):
        a, b = roads[i]
        adjacency_list[a].append(b)
        adjacency_list[b].append(a)

    array = []
    visited = set()

    def bfs(start):
        queue = deque([start])
        visited.add(start)

        while queue:
            node = queue.popleft()

            for neighbor in adjacency_list[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

    for i in range(1, n + 1):

        if i not in visited:
            array.append(i)
            bfs(i)

    print(len(array) - 1)

    for i in range(len(array) - 1):
        print(array[i], array[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