Connect cities

N, M = input("").split(" ")
N, M = int(N), int(M)

ADJ = [[] for _ in range(N)]

for i in range(M):
    a, b = input("").split(" ")
    a, b = int(a) - 1, int(b) - 1
    ADJ[a].append(b)
    ADJ[b].append(a)

seen = [-1] * N

def dfs(k, tag):
    if seen[k] != -1:
        return
    seen[k] = tag
    for x in ADJ[k]:
        dfs(x, tag)

nb_of_components = 0
for i in range(N):
    if seen[i] == -1:
        dfs(i, nb_of_components)
        nb_of_components += 1

components = [[] for _ in range(nb_of_components) ]

for i, tag in enumerate(seen):
    components[tag].append(i)

additions = []
current = components[0][0]

for i in range(1, nb_of_components):
    next = components[i][0]
    additions.append((current, next))
    next = current

print(len(additions))
for x, y in additions:
    print(f"{x+1} {y+1}")

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 24, in <module>
    dfs(i,...

Test 7

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 24, in <module>
    dfs(i,...

Test 8

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 24, in <module>
    dfs(i,...

Test 9

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 24, in <module>
    dfs(i,...

Test 10

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 24, in <module>
    dfs(i,...

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED