Connect cities

from time import time
import sys

sys.setrecursionlimit(int(1E5))

t0 = time()
cities, roads = [int(aa) for aa in input().strip().split(" ")]
# alreadyRoads = set([frozenset([int(aa) for aa in input().strip().split(" ")]) for _ in range(roads)])
alreadyRoads = [[int(aa)-1 for aa in input().strip().split(" ")] for _ in range(roads)]

def addSubItems(curItem, listIndex, roadsSetList, roadDict, checkedDict):
    # print("Checking", curItem)
    if checkedDict[curItem] != -1:
        return 0
    checkedDict[curItem] = listIndex
    if len(roadsSetList) <= listIndex:
        roadsSetList.append(set())
    
    if curItem in roadDict:
        roadsSetList[checkedDict[curItem]].update(roadDict[curItem])
    else:
        roadsSetList[checkedDict[curItem]] = {curItem}
        return 1
    
    for oneRoad in roadDict[curItem]:
        if checkedDict[oneRoad] != -1:
            continue
        addSubItems(oneRoad, listIndex, roadsSetList, roadDict, checkedDict)
    return 1

roadDict = {}
for start, end in alreadyRoads:
    if start in roadDict:
        roadDict[start].add(end)
    else:
        roadDict[start] = set([end])
        
    if end in roadDict:
        roadDict[end].add(start)
    else:
        roadDict[end] = set([start])

checkedDict = [-1]*cities
roadsSetList = []
counter = 0
for ii, ids in enumerate(checkedDict):
    counter += addSubItems(ii, counter, roadsSetList, roadDict, checkedDict)
# print(len(roadsSetList))

print(len(roadsSetList)-1)
zeroth = 0
for ii in roadsSetList[0]:
    zeroth = 0
    break

for ii in range(1,len(roadsSetList)):
    cur = 0
    for aa in roadsSetList[ii]:
        cur = aa
        break
    print(zeroth+1, cur+1)

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: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED