#include <bits/stdc++.h>

constexpr int N = 100005;

int n, m;
std::unordered_map<int, int> par[N];
std::unordered_map<int, std::vector<int>> graph[N];
int get_par(int i, int x) { return !par[i][x] ? x : par[i][x] = get_par(i, par[i][x]); }

int fa[N], dep[N];
void print(int i, int s, int t) {
    for (auto [x, g] : graph[i]) fa[x] = -1;
    const std::function<void(int, int)> dfs = [&](int u, int p) {
        fa[u] = p;
        dep[u] = dep[p] + 1;
        for (int v : graph[i][u]) if (fa[v] == -1) dfs(v, u);
    };
    dfs(t, 0);
    printf("%d", dep[s]);
    for (int u = s; u; u = fa[u]) printf(" %d", u);
    putchar('\n');
}

int main() {
    std::cin.sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T;
    std::cin >> T;
    while (T--) {
        std::cin >> n >> m;
        int k = (m + n - 2) / (n - 1);
        for (int i = 1; i <= n; i++) {
            par[i].clear();
            graph[i].clear();
        }
        for (int i = 1; i <= m; i++) {
            int x, y;
            std::cin >> x >> y;
            int l = 1, r = k + 1;
            while (l < r) {
                int mid = (l + r) >> 1;
                int px = get_par(mid, x), py = get_par(mid, y);
                if (px == py) l = mid + 1;
                else r = mid;
            }
            if (r <= k) {
                graph[r][x].push_back(y);
                graph[r][y].push_back(x);
                int px = get_par(r, x), py = get_par(r, y);
                par[r][px] = py;
            }
        }
        for (int i = 1; i <= n; i++) if (int j = get_par(k, i); j != i) {
            printf("%d %d\n", i, j);
            for (int o = 1; o <= k; o++) print(o, i, j);
            break;
        }
    }
    return 0;
}