Connect cities

# Get the number of cities and roads
n,m = [int(i) for i in input().split()]

# Get and process the roads
roads = set()
for i in range(m):
    a,b = [int(j) for j in input().split()]
    if a is b:
        continue
    elif a>b:
        a,b = b,a
    road = tuple((a,b))
    # if road in roads:
    #     continue
    # else:
    roads.add(road)

# Pregroup cities
groups = [{i+1} for i in range(n)]
for a,b in roads:
    groups[a-1].add(b)
    groups[b-1].add(a)

# for group in groups:
#     print(group)


unexplored = {i+1 for i in range(n)}
new_groups = []
while unexplored:
    current = unexplored.pop()
    new_groups.append(groups[current-1])
    
    while new_groups[-1].intersection(unexplored):
        i = new_groups[-1].intersection(unexplored).pop()
        new_groups[-1].update(groups[i-1])
        unexplored.remove(i)

# print("Result")
# for group in new_groups:
#     print(group)

print(len(new_groups)-1)
if len(new_groups) > 1:
    connections = [new_groups[i].pop() for i in range(len(new_groups))]

    origin = connections.pop(0)
    for i in connections:
        print(origin, i)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED