Connect cities

n, m = map(int, input().split())

adj = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())

    adj[a].append(b)
    adj[b].append(a)

visited = [False] * (n + 1)
representatives = []

for city in range(1, n + 1):

    if visited[city]:
        continue
    
    representatives.append(city)

    # DFS

    stack = [city]
    visited[city] = True

    while stack:
        u = stack.pop()

        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                stack.append(v)

print(len(representatives) - 1)

for i in range(1, len(representatives)):
    print(representatives[i - 1], representatives[i])

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