Connect cities

cities_num, roads_num = [int(x) for x in input().split()]
visited = [False for _ in range(cities_num+1)]
adj = [[]for _ in range(cities_num+1)] #5 empty lists



def addAdj(adjList, city, connected_city):
    adjList[city].append(connected_city)

def dfs(node):
    if visited[node]:
        return
    visited[node] = True
    for x in adj[node]:
        dfs(x)

def main():
    all_connected = False
    final_num = 0
    final_string = ""


    for i in range(roads_num):
        city, connected_city = [int(x) for x in input().split()]
        addAdj(adj, city, connected_city)
    while not all_connected:
        dfs(1)
        for i in range(1,cities_num+1):
            if not visited[i]:
                addAdj(adj, i-1, i)
                final_num += 1
                final_string += str(i-1)
                final_string += " "
                final_string += str(i)
                for j in range(len(visited)):
                    visited[j] = False
                break
            all_connected = True
    print(final_num)
    print(final_string)

if __name__ == "__main__":
    main()

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: 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: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER