Connect cities

n, m = [int(x) for x in input().split()]
roads = []
for i in range(m):
    roads.append([int(x) - 1 for x in input().split()])


class City:
    def __init__(self, n):
        self.n = n
        self.connected_cities = []

cities = []
for i in range(n):
    cities.append(City(i))

for road in roads:
    cities[road[0]].connected_cities.append(road[1])
    cities[road[1]].connected_cities.append(road[0])

new_roads = []

def build_road(n1, n2):
    cities[n1].connected_cities.append(n2)
    cities[n2].connected_cities.append(n1)
    new_roads.append((n1 + 1, n2 + 1))


def search(city: City, visited_cities):
    visited_cities[city.n] = True
    for connected_city in city.connected_cities:
        if connected_city not in visited_cities:
            search(cities[connected_city], visited_cities)
            return
    
    for i in range(n):
        if i not in visited_cities:
            build_road(city.n, i)
            search(cities[i], visited_cities)
    return

search(cities[0], {})
print(len(new_roads))
for road in new_roads:
    print(f'{road[0]} {road[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

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

Test 7

Verdict: RUNTIME ERROR

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

Test 8

Verdict: RUNTIME ERROR

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

Test 9

Verdict: RUNTIME ERROR

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

Test 10

Verdict: RUNTIME ERROR

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

Test 11

Verdict: RUNTIME ERROR

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

Test 12

Verdict: WRONG ANSWER