Задача № 3. Получи дерево.

#include <iostream>
#include <vector>

// Дан связный неориентированный граф без петель и кратных ребер. Разрешается удалять из него ребра. Требуется получить дерево.
// Решаем через поиск в глубину.


void dfs(int v, int n, std::vector<int> &used, std::vector<std::vector<int>> &g) {
    used[v] = 1;
    for (int i = 1; i <= n; i++) {
        if ((g[v][i] == 1) && (used[i] == 0)) {
            std::cout << v << " " << i << std::endl;
            dfs(i, n, used, g);
        }
    }
}

int main() {
    int n = 0, m = 0; // n, m - кол-во вершин, рёбер соответственно.
    std::cin >> n >> m;
    std::vector<std::vector<int>> g(n + 1, std::vector<int> (n + 1, 0));
    for (size_t i = 0; i < m; ++i) {
        int f = 0, t = 0;
        std::cin >> f >> t; // Концы одного ребра, нумерация начинается с 1.
        g[f][t] = 1;
        g[t][f] = 1;
    }
    std::vector<int> used(n + 1); // Вершины, в которых мы уже побывали.
    std::cout << std::endl;
    dfs(1, n, used, g);
    return 0;
}