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 = []
for i in range(len(trees)):
    if i + 1 >= len(trees):
        break
    
    new_roads.append((trees[i][0] + 1, trees[i+1][0] + 1))

print(len(new_roads))    
for r in new_roads:
    print(f'{r[0]} {r[1]}')

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