Connect cities

#!/usr/bin/env python3

'''Connect Cities'''

N,M = [int(x) for x in input().split()]
GRAPH = [[] for _ in range(N + 1)]
NOT_VISITED = set(range(2, N + 1))

def dfs(node):
    '''Depth-first search'''
    cities_to_visit = [node]
    while len(cities_to_visit) > 0:
        node = cities_to_visit[-1]
        if len(GRAPH[node]):
            next_node = GRAPH[node].pop()
            if next_node in NOT_VISITED:
                NOT_VISITED.remove(next_node)
                cities_to_visit.append(next_node)
        else:
            cities_to_visit.pop()

def main():
    '''Main'''
    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        GRAPH[a].append(b)
        GRAPH[b].append(a)

    solution = []

    dfs(1)
    while len(NOT_VISITED) > 0:
        node = NOT_VISITED.pop()
        solution.append((1, node))
        dfs(node)

    print(len(solution))
    for elt in solution:
        print(str(elt[0]) + ' ' + str(elt[1]))

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