Connect cities

from collections import defaultdict

if __name__ == "__main__":
    n, m = [int(x) for x in input().split(" ")]
    
    roads = defaultdict(list)
    for x in range(1, m + 1):
        s, e = [int(x) for x in input().split(" ")]
        roads[s].append(e)
        roads[e].append(s)
    
    visited = {}
    new_roads = []
    
    def dfs(x):
        if x in visited:
            return
        visited[x] = True
        for n in roads[x]:
            dfs(n) 

    for x in range(1, n + 1):
        if x in visited:
            continue
        new_roads.append(x)
        dfs(x)
    
    print(len(new_roads) - 1)
    for e in new_roads[1:]:
        print(1, e)

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 27, in <module>
    dfs(x)
  File "/box/input/code.py", line 21, in dfs
    dfs(n)
  File "/box/input/code.py", line 21, in dfs
    dfs(n)
  File "/box/input/code.py", line 21, in dfs
    dfs(n)
  [Previous line repeated 1538 more times]
  File "/box/input/code.py", line 16, in dfs
    def dfs(x):
RecursionError: maximum recursion depth exceeded

Test 7

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 27, in <module>
    dfs(x)
  File "/box/input/code.py", line 21, in dfs
    dfs(n)
  File "/box/input/code.py", line 21, in dfs
    dfs(n)
  File "/box/input/code.py", line 21, in dfs
    dfs(n)
  [Previous line repeated 1684 more times]
  File "/box/input/code.py", line 20, in dfs
    for n in roads[x]:
RecursionError: maximum recursion depth exceeded

Test 8

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 27, in <module>
    dfs(x)
  File "/box/input/code.py", line 21, in dfs
    dfs(n)
  File "/box/input/code.py", line 21, in dfs
    dfs(n)
  File "/box/input/code.py", line 21, in dfs
    dfs(n)
  [Previous line repeated 1492 more times]
RecursionError: maximum recursion depth exceeded

Test 9

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 27, in <module>
    dfs(x)
  File "/box/input/code.py", line 21, in dfs
    dfs(n)
  File "/box/input/code.py", line 21, in dfs
    dfs(n)
  File "/box/input/code.py", line 21, in dfs
    dfs(n)
  [Previous line repeated 1684 more times]
  File "/box/input/code.py", line 20, in dfs
    for n in roads[x]:
RecursionError: maximum recursion depth exceeded

Test 10

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 27, in <module>
    dfs(x)
  File "/box/input/code.py", line 21, in dfs
    dfs(n)
  File "/box/input/code.py", line 21, in dfs
    dfs(n)
  File "/box/input/code.py", line 21, in dfs
    dfs(n)
  [Previous line repeated 1684 more times]
  File "/box/input/code.py", line 20, in dfs
    for n in roads[x]:
RecursionError: maximum recursion depth exceeded

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED