Connect cities

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

g = {}
for i in range(1, n+1):
    g[i] = []

for i in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

visited = [False] * (n + 1)

def dfs(node, visited, temp):
    visited[node] = True
    temp.append(node)
    for neighbor in g[node]:
        if not visited[neighbor]:
            dfs(neighbor, visited, temp)

connected_components = []

for i in range(1, n+1):
    if not visited[i]:
        temp = []
        dfs(i, visited, temp)  # Perform DFS
        connected_components.append(temp)

k = len(connected_components)-1
print(k)
for i in range(k):
    print(str(connected_components[i][-1]) + " " + str(connected_components[i+1][0]))

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 "/box/input/code.py", line 26, in <module>
    dfs(i, visited, temp)  # Perform DFS
  File "/box/input/code.py", line 19, in dfs
    dfs(neighbor, visited, temp)
  File "/box/input/code.py", line 19, in dfs
    dfs(neighbor, visited, temp)
  File "/box/input/code.py", line 19, in dfs
    dfs(neighbor, visited, temp)
  [Previous line repeated 995 more times]
  File "/box/input/code.py", line 16, in dfs
    temp.append(node)
RecursionError: maximum recursion depth exceeded while calling a Python object

Test 7

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 26, in <module>
    dfs(i, visited, temp)  # Perform DFS
  File "/box/input/code.py", line 19, in dfs
    dfs(neighbor, visited, temp)
  File "/box/input/code.py", line 19, in dfs
    dfs(neighbor, visited, temp)
  File "/box/input/code.py", line 19, in dfs
    dfs(neighbor, visited, temp)
  [Previous line repeated 995 more times]
  File "/box/input/code.py", line 16, in dfs
    temp.append(node)
RecursionError: maximum recursion depth exceeded while calling a Python object

Test 8

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 26, in <module>
    dfs(i, visited, temp)  # Perform DFS
  File "/box/input/code.py", line 19, in dfs
    dfs(neighbor, visited, temp)
  File "/box/input/code.py", line 19, in dfs
    dfs(neighbor, visited, temp)
  File "/box/input/code.py", line 19, in dfs
    dfs(neighbor, visited, temp)
  [Previous line repeated 995 more times]
  File "/box/input/code.py", line 16, in dfs
    temp.append(node)
RecursionError: maximum recursion depth exceeded while calling a Python object

Test 9

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 26, in <module>
    dfs(i, visited, temp)  # Perform DFS
  File "/box/input/code.py", line 19, in dfs
    dfs(neighbor, visited, temp)
  File "/box/input/code.py", line 19, in dfs
    dfs(neighbor, visited, temp)
  File "/box/input/code.py", line 19, in dfs
    dfs(neighbor, visited, temp)
  [Previous line repeated 995 more times]
  File "/box/input/code.py", line 16, in dfs
    temp.append(node)
RecursionError: maximum recursion depth exceeded while calling a Python object

Test 10

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 26, in <module>
    dfs(i, visited, temp)  # Perform DFS
  File "/box/input/code.py", line 19, in dfs
    dfs(neighbor, visited, temp)
  File "/box/input/code.py", line 19, in dfs
    dfs(neighbor, visited, temp)
  File "/box/input/code.py", line 19, in dfs
    dfs(neighbor, visited, temp)
  [Previous line repeated 995 more times]
  File "/box/input/code.py", line 16, in dfs
    temp.append(node)
RecursionError: maximum recursion depth exceeded while calling a Python object

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED