Connect cities

def dfs(adj, not_visited, s):
    stack = [s]
    while len(stack) > 0:
        v = stack.pop()
        if v in not_visited:
            not_visited.discard(v)
            for u in adj[v]:
                stack.append(u)


def main():
    n, m = input().split(' ')
    n, m = int(n), int(m)

    not_visited = set()
    adj = []
    for i in range(n):
        not_visited.add(i)
        adj.append([])

    for i in range(m):
        a, b = input().split(' ')
        a, b = int(a)-1, int(b)-1
        adj[a].append(b)
        adj[b].append(a)

    edges = []
    prev = 0
    while len(not_visited) > 0:
        dfs(adj, not_visited, prev)
        if len(not_visited) > 0:
            itr = iter(not_visited)
            node = next(itr)
            edges.append((prev, node))
            prev = node
        else:
            break

    print(len(edges))
    for a, b in edges:
        print(f"{a+1} {b+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