Самым выгодным способом добавлять ребра будет добавление ребер между компонентами связности -- тогда с каждым новым ребром у нас будет становиться на одну компоненту связности меньше, потому что мы будем объединять тем самым две компоненты. Получается, что если у нас k компонент связности, то нужно добавить k-1 ребро. Для того чтобы вывести ребра которые мы "добавим в граф", сохраним по одной вершине из каждой компоненты, и соединим их ребрами по порядку.

Обойти компоненту связности можно с помощью dfs, будем запускать его по порядку от каждой непосещенной вершины, и тогда мы запустимся ровно от одной вершины в каждой компоненте связности. Кол-во этих вершин и будет кол-вом компонент, а так же их мы и можем сохранить в качестве вершин "представителей", которые мы будем соединять для ответа.

Пример кода на python:
def dfs(h):
    used[h] = 1
    for e in g[h]:
        if not used[e]:
            dfs(e)

n, m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    x -= 1, y -= 1
    g[x].append(y)
    g[y].append(x)
answ = [] #список с вершинкой из каждой компоненты
used = [0] * n
for i in range(n):
    if not used[i]:
        dfs(i)
        answ.append(i + 1)
print(len(answ) - 1)
for i in range(1, len(answ)):
    print(answ[i - 1], answ[i])