Dfs обходит ребра, которые образуют дерево. Это дерево называется дерево обхода, или дерево dfs. Давайте возьмем его в ответ, то есть возьмем все ребра по которым мы проходим в dfs.

Пример кода на python:
def dfs(h):
    used[h] = 1
    for e in g[h]:
        if not used[e]:
            answ.append((h + 1, e + 1))
            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)
used = [0] * n
answ = []
dfs(0)
for e in answ:
    print(*e)