Connect cities

n, m = map(int, input().split())
roads = [tuple(map(int, input().split())) for _ in range(m)]

chunk_counter = 0
chunks = {}
chunk_roads = {}
roads_to_build = {}
for road_a, road_b in roads:
    if road_a not in chunks and road_b not in chunks:
        chunk_counter += 1
        chunks[road_a] = chunk_counter
        chunks[road_b] = chunk_counter
        
        chunk_roads[chunk_counter] = [road_a, road_b]
        if chunk_counter != 1:
            roads_to_build[frozenset([chunk_counter - 1, chunk_counter])] = (chunk_roads[chunk_counter - 1][0], road_a)
    elif road_a in chunks and road_b not in chunks:
        chunks[road_b] = chunks[road_a]

        chunk_roads[chunks[road_a]].append(road_b)
    elif road_b in chunks and road_a not in chunks:
        chunks[road_a] = chunks[road_b]

        chunk_roads[chunks[road_b]].append(road_a)
    elif road_a in chunks and road_b in chunks:
        if chunks[road_a] != chunks[road_b] and frozenset([chunks[road_a], chunks[road_b]]) in roads_to_build:
            del roads_to_build[frozenset([chunks[road_a], chunks[road_b]])]
    else:
        raise Exception('?')

for city in range(1, n + 1):
    if city not in chunks:
        chunk_counter += 1
        chunks[city] = chunk_counter
        chunk_roads[chunk_counter] = [city]

        if city != 1:
            roads_to_build[frozenset([1, chunk_counter])] = (chunk_roads[1][0], city)

print(len(roads_to_build))
for road_a, road_b in roads_to_build.values():
    print(road_a, road_b)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED