#include<iostream>
#include<cstring>
#include<vector>
#include<numeric>
using namespace std;
using LL = long long;

struct DSU{
    vector<int> p;
    DSU(int n) : p(n + 1){
        iota(p.begin(), p.end(), 0);
    }

    int find(int x){
        return p[x] == x ? x : p[x] = find(p[x]);
    }

    bool same(int x, int y) { 
        return find(x) == find(y); 
    }

    bool merge(int x, int y){
        x = find(x), y = find(y);
        if (x == y) return false;
        p[y] = x;
        return true;
    }
};

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        int k = (m + n - 2) / (n - 1);
        vector<DSU> dsu(k, DSU(n));
        int p1 = -1, p2 = -1;
        vector<vector<vector<int> > > g(k, vector<vector<int> >(n + 1));
        for(int i = 0; i < m; i++){
            int a, b;
            cin >> a >> b;
            if (p1 != -1) continue;
            int l = 0, r = k;
            while(l < r){
                int mid = (l + r) / 2;
                if (!dsu[mid].same(a, b)) r = mid;
                else l = mid + 1;
            }
            if (r < k){
                dsu[r].merge(a, b);
                g[r][a].push_back(b);
                g[r][b].push_back(a);
            }
            if (r >= k - 1){
                p1 = a, p2 = b;
            }
        }
        vector<int> v(n + 1, -1);
        cout << p1 << ' ' << p2 << '\n';
        for(int i = 0; i < k; i++){
            vector<int> path, ans;

            auto dfs = [&](auto &&dfs, int u) -> void {
                v[u] = i;
                path.push_back(u);
                if (u == p2) ans = path;
                for(auto j : g[i][u]){
                    if (v[j] != i){
                        dfs(dfs, j);
                    }
                }
                path.pop_back();
            };

            dfs(dfs, p1);
            for(auto x : ans) cout << x << ' ';
            cout << '\n';
        }
    }

}