Connect cities

import sys

dbg = 0


# strict int
def sint(x):
    if isinstance(x, str):
        return int(x)
    if x.is_integer():
        return int(x)
    raise ValueError


def ep(*args, **kwargs):
    if dbg:
        print(*args, file=sys.stderr, **kwargs)


def p(**kwargs):
    ep(", ".join([f"{k} = {v}" for (k, v) in kwargs.items()]))


# n = sint(input())
# p_n = [sint(h) for i, h in enumerate(input().split(" "))]
# p(n=n, p_n=p_n)
[n, m] = [int(x) for x in input().split(" ")]
p(n=n, m=m)
roads = set([frozenset([sint(x) for x in input().split(" ")]) for i in range(m)])
p(roads=roads)


# we can build a list of islands and then connect the islands together one by one
# the number of required roads is always islands-1
#
# we can loop through all the... roads? cities? both?
islands = set[frozenset]([frozenset([x + 1]) for x in range(n)])
for r in roads:
    [c1, c2] = r
    ild_w_c1 = next((x for x in islands if c1 in x))
    ild_w_c2 = next((x for x in islands if c2 in x))
    # if neither of the cities are in the islands set
    # if ild_w_c1 is None and ild_w_c2 is None:
    #     ep("adding new island", [c1, c2])
    #     islands.add(frozenset([c1, c2]))
    if ild_w_c1 is ild_w_c2:
        continue
    # elif ild_w_c1 is None:
    #     assert ild_w_c2 is not None
    #     islands.remove(ild_w_c2)
    #     ep("adding city", c1, "to island", ild_w_c2)
    #     islands.add(ild_w_c2.union([c1]))
    # elif ild_w_c2 is None:
    #     assert ild_w_c1 is not None
    #     islands.remove(ild_w_c1)
    #     ep("adding city", c2, "to island", ild_w_c1)
    #     islands.add(ild_w_c1.union([c2]))
    else:
        islands.remove(ild_w_c1)
        islands.remove(ild_w_c2)
        ep("connecting", ild_w_c1, "with", ild_w_c2)
        islands.add(ild_w_c1.union(ild_w_c2))
p(islands=islands)

hub = islands.pop()
hub_city = next(iter(hub))
new_roads = set()
for i in islands:
    gate_city = next(iter(i))
    new_roads.add((hub_city, gate_city))

print(len(new_roads))
for n in new_roads:
    print(*n)

# new_roads = set()
# for c1 in range(n):
#     for c2 in range(n):
#         if c1 == c2:
#             continue
#         road = frozenset([c1 + 1, c2 + 1])
#         p(road=road)
#         if road not in roads:
#             new_roads.add(road)
# print(len(new_roads) + len(roads))
# for r in new_roads:
#     print(*r)

Test 1

Verdict: RUNTIME ERROR

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

Test 2

Verdict: RUNTIME ERROR

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

Test 3

Verdict: RUNTIME ERROR

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

Test 4

Verdict: RUNTIME ERROR

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

Test 5

Verdict: RUNTIME ERROR

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

Test 6

Verdict: RUNTIME ERROR

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

Test 7

Verdict: RUNTIME ERROR

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

Test 8

Verdict: RUNTIME ERROR

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

Test 9

Verdict: RUNTIME ERROR

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

Test 10

Verdict: RUNTIME ERROR

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

Test 11

Verdict: RUNTIME ERROR

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

Test 12

Verdict: RUNTIME ERROR

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