Connect cities

if __name__ == "__main__":
    n, m = [int(x) for x in input().split(" ")]
    
    roads = {}
    for x in range(1, m + 1):
        s, e = [int(x) for x in input().split(" ")]
        if not (s in roads):
            roads[s] = []
        if not (e in roads):
            roads[e] = []
        roads[s].append(e)
        roads[e].append(s)
    
    visited = {}
    new_roads = []
    
    # def dfs(x):
    #     if x in visited:
    #         return
    #     visited[x] = True
    #     if not x in roads:
    #         return
    #     for n in roads[x]:
    #         dfs(n) 

    for x in range(1, n + 1):
        if x in visited:
            continue
        new_roads.append(x)
        # dfs(x)
        
        stack = [x]
        while len(stack) > 0:
            y = stack.pop()
            if y in visited:
                continue
            visited[y] = True
            if not y in roads:
                continue
            for n in roads[y]:
                stack.append(n)
            
    
    print(len(new_roads) - 1)
    for e in new_roads[1:]:
        print(1, e)

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