Connect cities

n, m = [int(x) for x in input().split()]
roads = []
for i in range(m):
    roads.append([int(x) - 1 for x in input().split()])

class Node:
    def __init__(self, n):
        self.n = n
        self.edges = []
        self.discovered = False


nodes = []
for i in range(n):
    nodes.append(Node(i))

for i in range(len(roads)):
    nodes[roads[i][0]].edges.append(roads[i][1])
    nodes[roads[i][1]].edges.append(roads[i][0])

trees = []
def bfs(i, tree_i):
    nodes[i].discovered = True
    trees[tree_i].append(i) 
    for edge in nodes[i].edges:
        if nodes[edge].discovered:
            continue
        bfs(edge, tree_i)
def construct_trees():
        
    for i in range(len(nodes)):
        if nodes[i].discovered: continue
        trees.append([])
        bfs(i, len(trees) - 1)

construct_trees()
new_roads = []
k = 0
new_road_string = ''
for i in range(len(trees)):
    if i + 1 >= len(trees):
        break
    
#    new_roads.append((trees[i][0] + 1, trees[i+1][0] + 1))
    new_road_string += str(trees[i][0] + 1) + " " + str(trees[i+1][0] + 1) + "\n"
    k += 1
new_road_string = new_road_string[:-1]
print(k)
print(new_road_string)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED