Connect cities

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [0] * n

    def find(self, x):
        while x != self.parent[x]:
            x = self.parent[x]

        return x
    
    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return

        if self.size[a] > self.size[b]:
            self.parent[b] = a
        elif self.size[b] > self.size[a]:
            self.parent[a] = b
        else:
            self.parent[b] = a
            self.size[a] += 1

n, m = map(int, input().split())
roads = [tuple(map(int, input().split())) for _ in range(m)]

uf = UnionFind(n)

for road_a, road_b in roads:
    uf.unite(road_a - 1, road_b - 1)

cities_in_chunk = {}
for city in range(n):
    chunk = uf.find(city)

    if chunk not in cities_in_chunk:
        cities_in_chunk[chunk] = []
    cities_in_chunk[chunk].append(city)

chunks = list(cities_in_chunk.keys())
print(len(chunks) - 1)
for i in range(1, len(chunks)):
    print(cities_in_chunk[chunks[i - 1]][0] + 1, cities_in_chunk[chunks[i]][0] + 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