Shared code

import sys

input = sys.stdin.readline


def solve(n, adjlist):
    visited = [False] * n

    def dfs(node):
        st = [node]
        while st:
            node = st.pop()
            if not visited[node]:
                visited[node] = True
                st.extend(adjlist[node])

    ans = []
    for i in range(n):
        if not visited[i]:
            dfs(i)
            ans.append(i)

    print(len(ans) - 1)
    out = []
    for i in range(len(ans) - 1):
        out.append(f"{ans[i] + 1} {ans[i + 1] + 1}")
    print("\n".join(out))


def main():
    n, m = list(map(int, input().split()))
    edges = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
    adjlist = [[] for _ in range(n)]
    for u, v in edges:
        adjlist[u].append(v)
        adjlist[v].append(u)
    solve(n, adjlist)


main()