Connect cities

def main():
    cities, roads = [int(x) for x in input().split()]
    adj_list = {k:[] for k in range(1, cities+1)}
    visited = [False for _ in range(cities+1)]
    new_roads = []
    stack = []

    for _ in range(roads):
        city1,city2 = [int(x) for x in input().split()]
        adj_list[city1].append(city2)
        adj_list[city2].append(city1) 


    for city in adj_list:
        if not visited[city]:
            stack.append(city)
            visited[city] = True

            if city != 1:
                new_roads.append([1, city])

            while stack:
                aux = stack.pop()
                for x in adj_list[aux]:
                    if not visited[x]:
                        stack.append(x)
                        visited[x] = True
            
                    
    print(len(new_roads))
    for x in new_roads:
        print(f"{x[0]} {x[1]}")

main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED