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.roads = [] 

cities = []
for i in range(n):
    cities.append(City(n))
for road in roads:
    cities[road[0]].roads.append(road[1])
    cities[road[1]].roads.append(road[0])

def find_deepest_path(city_i, cities, visited_cities, depth):
    city = cities[city_i]
    visited_cities[city_i] = True
    if not city.roads:
        return city_i, visited_cities, depth
    
    maxd = depth
    maxd_i = city_i
    for connected_city_i in city.roads:
        if connected_city_i not in visited_cities:
            i, visited_cities, d = find_deepest_path(connected_city_i, cities, visited_cities, depth+1)
            if d >= maxd:
                maxd = d
                maxd_i = i
    return maxd_i, visited_cities, maxd

created_roads = []
visited_cities = {}
last_new_i = -1
for i in range(n):

    if i not in visited_cities:
        new_i, visited_cities, _ = find_deepest_path(i, cities, visited_cities, 0)
        if last_new_i != -1:
            created_roads.append([last_new_i + 1, i + 1])
        last_new_i = new_i


print(len(created_roads))    
for r in created_roads:
    print(f'{r[0]} {r[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 40, in <module>
    new_i,...

Test 7

Verdict: RUNTIME ERROR

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

Test 8

Verdict: RUNTIME ERROR

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

Test 9

Verdict: RUNTIME ERROR

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

Test 10

Verdict: RUNTIME ERROR

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

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED