Connect cities

num_cities, num_roads = [int(x) for x in input().split()]
to_visit = list(range(1, num_cities + 1))
neightbours = [to_visit.copy() for _ in range(num_cities + 1)]
paths = []
visited = []
og_paths = []

for _ in range(num_roads):
    x1, x2 = [int(x) for x in input().split()]
    neightbours[x1].insert(0, x2)
    neightbours[x2].insert(0, x1)
    og_paths.append([x1, x2])
    og_paths.append([x2, x1])

def dfs(node: int) -> bool:
    if len(paths) == num_cities - 1:
        return True
    visited.append(node)
    for x in neightbours[node]:
        if x not in visited:
            paths.append([node, x])
            if dfs(x):
                return True
    return False

dfs(to_visit[0])
print(f"{len(paths) - num_roads}")
for path in paths:
    if path not in og_paths:
        print(f"{path[0]} {path[1]}")

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: RUNTIME ERROR

Test 7

Verdict: RUNTIME ERROR

Test 8

Verdict: RUNTIME ERROR

Test 9

Verdict: RUNTIME ERROR

Test 10

Verdict: RUNTIME ERROR

Test 11

Verdict: RUNTIME ERROR

Test 12

Verdict: WRONG ANSWER