#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

vector<int> g[N];
int n, m, k, fa[N], dep[N];

struct DSU {
  vector<int> p;
  vector<pair<int, int>> e;
  
  DSU(int _n = 0) {
    p.resize(_n + 1);
    iota(p.begin(), p.end(), 0);
  }
  
  int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
  void merge(int u, int v) {
    int pu = find(u), pv = find(v);
    if (pu == pv) return;
    e.emplace_back(u, v);
    p[pu] = pv;
  }
  bool check(int x, int y) { return find(x) == find(y); }
  void dfs(int u, int p) {
    fa[u] = p, dep[u] = dep[p] + 1;
    for (int v : g[u]) if (v != p) dfs(v, u);
  }
  void print(int u, int v) {
    for (int i = 1; i <= n; i++) g[i].clear();
    for (auto [x, y] : e) {
      g[x].emplace_back(y);
      g[y].emplace_back(x);
    }
    dfs(v, 0);
    cout << dep[u] << ' ';
    while (u) {
      cout << u << ' ';
      u = fa[u];
    }
    cout << '\n';
  }
};

void solve() {
  cin >> n >> m, k = (m + n - 2) / (n - 1);
  vector<DSU> G(k, DSU(n));
  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 = G.size();
    while (l <= r) {
      int m = (l + r) / 2;
      if (G[m].check(u, v)) l = m + 1;
      else pos = m, r = m - 1;
    }
    G[pos].merge(u, v);
    if (pos == k - 1) {
      print(u, v);
      return;
    }
  }
}

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