Connect cities

N, M = [ int(x) for x in input("").split(" ") ]
ROADS = [ [ int(x)-1 for x in input("").split(" ") ] for _ in range(M) ]
 
def build_adjacency(n: int, roads: list[tuple[int, int]]) -> list[list[int]]:
 
    result: list[list[int]] = [ [] for _ in range(n) ]
 
    for a, b in roads:
        result[a].append(b)
        result[b].append(a)
    
    return result
 
def build_components(n: int, adj: list[list[int]]) -> list[list[int]]:
 
    """
    def dfs(x: int, mark: list[int], id: int):
        if mark[x] != -1:
            return
        mark[x] = id
        for y in adj[x]:
            dfs(y, mark, id)
    """
    
    def dfs_iterative(x: int, mark: list[int], id: int):
 
        stack = [x]
        while len(stack) > 0:
            e = stack.pop()
            if mark[e] != -1:
                continue
            mark[e] = id
            for y in adj[e]:
                stack.append(y)
    
    id = 0
    mark = [-1] * n
 
    for i in range(n):
        if mark[i] == -1:
            dfs_iterative(i, mark, id)
            id += 1
 
    result: list[list[int]] = [ [] for _ in range(id) ]
 
    for i in range(n):
        result[mark[i]].append(i)
 
    return result
 
def build_paths(components: list[list[int]]) -> tuple[int, list[tuple[int, int]]]:
 
    k = len(components) - 1
    paths: list[tuple[int, int]] = [None] * k
 
    for i in range(1, k+1):
        paths[i-1] = (components[0][0], components[i][0])
 
    return k, paths
 
def solve(n: int, roads: list[tuple[int, int]]):
    k, paths = build_paths(build_components(n, build_adjacency(n, roads)))
    print(k)
    for a, b in paths:
        print(f"{a+1} {b+1}")
 
solve(N, ROADS)

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