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):
    if checkedDict[curItem] != -1:
        # print("Discarded", curItem)
        return 0
    # print("Checking", curItem)
    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]:
        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)

# print(ids)
# addSubItems(curItem=)

# doneList = [False]*counter
# for city in range(1, cities):
#     if roadsDict[city] == -1:
#         roadsDict[city] = counter
#         counter += 1
    

# print(roadsDict)
exit()
t1 = time()
roadGroups = []
# aloneRoads = {cit: True for cit in range(1,cities+1)}
# print(aloneRoads)
for startCity, endCity in alreadyRoads:
    flagged = False
    for group in roadGroups:
        if (startCity in group) and (endCity in group):
            pass
        elif (startCity in group):
            flagged = True
            group.add(endCity)
            # aloneRoads[endCity] = False
        elif (endCity in group):
            flagged = True
            group.add(startCity)
            # aloneRoads[startCity] = False
    if not flagged:
        roadGroups.append(set([startCity,endCity]))
        # aloneRoads[endCity] = False
        # aloneRoads[startCity] = False

for ii in range(cities):
    pass

# roadsLeft = roads*(1+roads)/2 - roads
t2 = time()
print(t1-t0,t2-t1)
# aloneRoadsList = [set([road]) for road in aloneRoads]
# roadGroups += [key for key in aloneRoads if aloneRoads[key]]
# print(aloneRoads)
# print(roadGroups)

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