#include<bits/stdc++.h>
using namespace std;

#define endl "\n"

const int MAXN = 4e5 + 3;

vector <int> I[MAXN];
vector <int> E[MAXN];

int F[MAXN], J[MAXN];

int getfa(int u){
    return u == F[u] ? u : F[u] = getfa(F[u]);
}

vector <int> ANS;

bool dfs(int u, int f, int t){
    // cout << u << " " << t << endl;
    if(u == t){
        ANS.push_back(J[u]);
        return true;
    }
    for(auto &v: E[u]) if(v != f){
        if(dfs(v, u, t)){
            ANS.push_back(J[u]);
            return true;
        }
    }
    return false;
}

int main(){
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    for(int _ = 1;_ <= T;++ _){
        int n, m;
        cin >> n >> m;
        int k = m / (n - 1) + !!(m % (n - 1));

        int o = 0;

        for(int i = 1;i <= k;++ i){
            I[i].resize(n + 1);
            for(int j = 1;j <= n;++ j){
                I[i][j] = ++ o;
                J[o] = j;
                F[o] = o;
            }
        }

        int ansu = -1, ansv = -1;

        for(int i = 1;i <= m;++ i){
            int u, v;
            cin >> u >> v;

            int p = 0;

            for(int j = 20;j >= 0;-- j){
                if((p | 1 << j) <= k){
                    int pp = p | 1 << j;
                    int fau = getfa(I[pp][u]);
                    int fav = getfa(I[pp][v]);

                    if(fau == fav){
                        p = pp;
                    }
                }
            }

            if(p == k)
                continue;
            
            ++ p;

            int x = I[p][u], y = I[p][v];
            E[x].push_back(y);
            E[y].push_back(x);

            F[getfa(x)] = getfa(y);

            if(p == k){
                ansu = u;
                ansv = v;
            }
        }

        assert(ansu != -1);

        cout << ansu << " " << ansv << endl;
        for(int i = 1;i <= k;++ i){
            ANS.clear();
            dfs(I[i][ansv], 0, I[i][ansu]);

            cout << ANS.size();
            for(auto &u: ANS)
                cout << " " << u;
            cout << endl;
        }

        for(int i = 1;i <= o;++ i)
            E[i].clear();
    }

    return 0;
}
/*
1
4 7
1 2
2 3
3 4
4 1
1 3
2 4
1 4
*/