Connect cities

import sys
sys.setrecursionlimit(2*10**5)

n, m = map(int, sys.stdin.readline().split())

parent = list(range(n))

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

def union(x, y):
    rx, ry = find(x), find(y)
    if rx != ry:
        parent[ry] = rx

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    union(a-1, b-1)

components = {find(i) for i in range(n)}
components = list(components)

print(len(components)-1)
for i in range(1, len(components)):
    print(components[i-1]+1, components[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