Connect cities

from collections import deque
used = []
comp = []
n, m = map(int, input().split())
 
g = [[] for i in range(n)]
 
for i in range(m):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
 
c = 0
clique = [-1] * n
 
def bfs(v):
    global g, clique
    queue = deque([v])
    while queue:
        node = queue.popleft()
        for w in g[node]:
            if clique[w] == -1:
                clique[w] = clique[v]
                queue.append(w)
 
for v in range(n):
    if clique[v] == -1:
        clique[v] = c
        c += 1
        bfs(v)
 
# print(clique)
 
clique_sorted = [(clique[i], (i + 1)) for i in range(n)]
clique_sorted.sort()
# print(clique_sorted)
print(c - 1)
i = 1
while i < n:
    if clique_sorted[i][0] != clique_sorted[i - 1][0]:
        print(clique_sorted[i][1], clique_sorted[i - 1][1])
    i += 1
 

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