#include <bits/stdc++.h>

const int N = 2e5 + 5;
std::vector<int> g[N];
int n, m, dep[N], fa[N];
bool vis[N];

struct cmp {
  bool operator () (const int &a, const int &b) const {
    return dep[a] > dep[b];
  }
};

void solve() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) g[i].clear();

  for (int u, v, i = 1; i <= m; i++) {
    scanf("%d%d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }

  memset(vis + 1, 0, n * sizeof(bool));
  auto dfs = [&](int x, int f, auto &dfs) -> void {
    if (vis[x]) return;
    vis[x] = 1, dep[x] = dep[f] + 1, fa[x] = f;
    for (auto y : g[x]) dfs(y, x, dfs);
  };
  dfs(1, 0, dfs);

  for (int i = 1;i <= n; i++)
    printf("%d ", fa[i]);
  puts("");

  int t = ceil(sqrt(n));
  std::vector<int> S;
  
  std::set<int, cmp> cur;
  for (int i = 1; i <= n; i++) cur.insert(i);

  while (cur.size() > 1u) {
    int x = *cur.begin();
    // cur.erase(x);
    printf("%d ", x);

    for (int i = 0; i < t; i++)
      if (x != 1) x = fa[x]; else break;
    printf(" -> %d\n", x);
    auto del = [&](int x, auto &del) {
      printf(" del %d\n", x);
      if (!cur.count(x)) return;
      cur.erase(x);
      for (auto y : g[x]) {
        printf(" > -> %d\n", y);
        if (fa[y] == x) del(y, del);
      }
    };
    del(x, del);

    S.push_back(x);
    cur.insert(x);

    for (int i = 0; i < 1e9; i++);
  }

  assert(S.size() <= t);
  printf("%u\n", S.size());
  for (auto x : S) printf("%d ", x);
  puts("");
}
/*
9 8
1 2
2 3
3 4
3 5
3 6
3 7
3 8
3 9

1
10 11
1 2
2 3
2 4
4 5
5 6
5 7
6 7
7 8
8 9
8 10
9 10
*/

signed main() {
  int t;
  scanf("%d", &t);
  while (t--) solve();
}

  File "answer.code", line 42
    while (cur.size() > 1u) {
                        ^
SyntaxError: invalid decimal literal