Connect cities

numberofcities, numberofroads = [int(x) for x in input().split()]
roads = [[] for _ in range(numberofcities)]
Connected = [False] * numberofcities

for i in range(0, numberofroads):
    fullinput = [int(x) for x in input().split()]
    roads[fullinput[0] - 1].append(fullinput[1])
    roads[fullinput[1] - 1].append(fullinput[0])

print(numberofcities - 1 - numberofroads)

starting = 0
for i in range(0, len(roads)):
    if len(roads[i]) != 0: 
        starting = i
        break
Connected[starting] = True

def findConnections(starting):
    for item in roads[starting]:
        if (Connected[item - 1] == False):
            Connected[item - 1] = True
            findConnections(item - 1)

while False in Connected:
    findConnections(starting)
    if False in Connected:
        falseIndex = Connected.index(False)
        maxnumberconnections = len(roads[falseIndex])
        for number in [x for x in Connected if x == False]:
            if len(roads[number]) > maxnumberconnections:
                falseIndex = number
                maxnumberconnections = len(roads[number])
        print(falseIndex + 1, Connected.index(True) + 1)
        Connected[falseIndex] = True
        starting = falseIndex

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: RUNTIME ERROR

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

Test 7

Verdict: RUNTIME ERROR

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

Test 8

Verdict: RUNTIME ERROR

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

Test 9

Verdict: RUNTIME ERROR

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

Test 10

Verdict: RUNTIME ERROR

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

Test 11

Verdict: TIME LIMIT EXCEEDED

Test 12

Verdict: TIME LIMIT EXCEEDED