Connect cities

import sys

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

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]) != 1: 
        starting = i
        Connected[starting] = True
        break

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)
        print(falseIndex + 1, Connected.index(True) + 1)
        Connected[falseIndex] = True
        starting = falseIndex

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

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: TIME LIMIT EXCEEDED

Test 12

Verdict: WRONG ANSWER