#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

struct DSU {
  int p[N];
  
  DSU(int _n = 0) {
    iota(p + 1, p + _n + 1, 1);
  }
  pair<int, int> find(int x) {
    if (p[x] == x) return {x, 0};
    auto [f, d] = find(p[x]);
    return {f, d + 1};
  }
  void merge(int x, int y) {
    auto px = find(x), py = find(y);
    if (px.second > py.second) swap(px, py);
    p[px.first] = py.first;
  }
  bool check(int x, int y) { return find(x).first == find(y).first; }
  void print(int u, int v) {
    auto pu = find(u), pv = find(v);
    vector<int> uP, vP; 
    if (pu.second > pv.second) {
      for (int i = 0; i < pu.second - pv.second; i++) {
        uP.emplace_back(u);
        u = p[u];
      }
    } else {
      for (int i = 0; i < pv.second - pu.second; i++) {
        vP.emplace_back(v);
        v = p[v];
      }
    }
    while (u != v) {
      uP.emplace_back(u);
      vP.emplace_back(v);
      u = p[u], v = p[v];
    }
    reverse(vP.begin(), vP.end());
    cout << uP.size() + vP.size() + 1 << ' ';
    for (int x : uP) cout << x << ' ';
    cout << u << ' ';
    for (int x : vP) cout << x << ' ';
    cout << '\n';
  }
};

void solve() {
  int n, m, k;
  cin >> n >> m, k = (m + n - 2) / (n - 1);
  vector<DSU> G;
  vector<pair<int, int>> e(m);
  for (auto &[u, v] : e) cin >> u >> v;
  auto print = [&](int u, int v) {
    cout << u << ' ' << v << '\n';
    for (auto S : G) S.print(u, v);
  };
  for (auto [u, v] : e) {
    int l = 0, r = (int)G.size() - 1, pos = -1;
    while (l <= r) {
      int m = (l + r) / 2;
      if (G[m].check(u, v)) l = m + 1;
      else pos = m, r = m - 1;
    }
    if (pos == -1) {
      DSU S(n);
      S.merge(u, v);
      G.emplace_back(S);
      if (G.size() == k) {
        print(u, v);
        return;
      }
    } else G[pos].merge(u, v);
  }
  vector<DSU>().swap(G);
}

int main() {
  // freopen("1.in", "r", stdin);
  cin.tie(0)->sync_with_stdio(0);
  int T;
  cin >> T;
  while (T--) solve();
  return 0;
}