#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


int N, M;
vector<int> A, B;

int main() {
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d%d", &N, &M);
    A.resize(M);
    B.resize(M);
    for (int i = 0; i < M; ++i) {
      scanf("%d%d", &A[i], &B[i]);
      --A[i];
      --B[i];
    }
// cerr<<"N = "<<N<<", A = "<<A<<", B = "<<B<<endl;
    
    vector<vector<int>> G(N);
    for (int i = 0; i < M; ++i) {
      G[A[i]].push_back(i);
      G[B[i]].push_back(i);
    }
    vector<int> deg(N);
    vector<int> leaf(N, 0);
    for (int u = 0; u < N; ++u) {
      deg[u] = G[u].size();
      if (deg[u] == 1) {
        const int i = G[u][0];
        const int v = A[i] ^ B[i] ^ u;
        ++leaf[v];
      }
    }
    
    /*
      delete edge?
      - no isol
      - no adj >= 3 leaves
    */
    vector<int> del(M, 0);
    auto rebuild = [&](int u) -> void {
      vector<int> tmp;
      for (const int i : G[u]) if (!del[i]) tmp.push_back(i);
      G[u] = tmp;
      assert((int)G[u].size() == deg[u]);
    };
    for (int i = 0; i < M; ++i) {
      const int a = A[i];
      const int b = B[i];
      if ([&]() -> bool {
        int vsLen = 0;
        int vs[2];
        for (const int u : {a, b}) {
          if (deg[u] == 1) {
            return false;
          } else if (deg[u] == 2) {
            const int j = G[u][0] ^ G[u][1] ^ i;
            const int v = A[j] ^ B[j] ^ u;
            if (leaf[v] + 1 > 2) {
              return false;
            }
            vs[vsLen++] = v;
          }
        }
        if (vsLen == 2 && vs[0] == vs[1] && leaf[vs[0]] + 2 > 2) {
          return false;
        }
        return true;
      }()) {
        del[i] = 1;
        for (const int u : {a, b}) {
          --deg[u];
          if (deg[u] <= 2) {
            rebuild(u);
          }
          if (deg[u] == 1) {
            const int j = G[u][0];
            const int v = A[j] ^ B[j] ^ u;
            ++leaf[v];
            // assert(leaf[v] <= 2);
          }
        }
// cerr<<"  del "<<i<<"; "<<a<<" "<<b<<": "<<deg<<" "<<leaf<<endl;
      }
    }
    for (int u = 0; u < N; ++u) {
      rebuild(u);
    }
// cerr<<"del = "<<del<<", G = "<<G<<", deg = "<<deg<<", leaf = "<<leaf<<endl;
    
    int now[2] = {};
    vector<int> col(N, -1);
    auto paint = [&](int u, int c) -> void {
      ++now[c];
      col[u] = c;
    };
    for (int u = 0; u < N; ++u) if (deg[u] >= 3 || (deg[u] == 2 && leaf[u] == 2)) {
      assert(!~col[u]);
      vector<int> vss[2];
      for (const int i : G[u]) {
        const int v = A[i] ^ B[i] ^ u;
        assert(deg[v] <= 2);
        if (deg[v] == 2) {
          const int j = G[v][0] ^ G[v][1] ^ i;
          const int w = A[j] ^ B[j] ^ v;
          if (~col[w]) {
            vss[col[w]].push_back(v);
          }
        }
      }
      /*
        c   - c^1 - u:c
        c^1 -  ?  - u:c
                    u:c - leaf:c^1
      */
      for (int c = 0; c < 2; ++c) {
        for (int x = 0; x <= (int)vss[c^1].size(); ++x) {
          int tmp[2] = {now[0], now[1]};
          tmp[c] += 1;
          tmp[c^1] += leaf[u];
          tmp[c^1] += (int)vss[c].size();
          tmp[c] += (int)vss[c^1].size() - x;
          tmp[c^1] += x;
          if (abs(tmp[0] - tmp[1]) <= 1) {
            paint(u, c);
            for (const int i : G[u]) {
              const int v = A[i] ^ B[i] ^ u;
              if (deg[v] == 1) {
                paint(v, c^1);
              }
            }
            for (const int v : vss[c]) {
              paint(v, c^1);
            }
            for (int j = 0; j < (int)vss[c^1].size(); ++j) {
              paint(vss[c^1][j], (j < x) ? (c^1) : c);
            }
            assert(now[0] == tmp[0]);
            assert(now[1] == tmp[1]);
            goto found;
          }
        }
      }
      assert(false);
     found:{}
    }
    for (int u = 0; u < N; ++u) if (!~col[u]) {
      assert(deg[u] == 1);
      const int i = G[u][0];
      const int v = A[i] ^ B[i] ^ u;
      assert(!~col[v]);
      assert(deg[v] == 1);
      paint(u, 0);
      paint(v, 1);
    }
    
    if (now[0] < now[1]) {
      swap(now[0], now[1]);
      for (int u = 0; u < N; ++u) {
        col[u] ^= 1;
      }
    }
    int ou = 0;
    for (int u = 0; u < N; ++u) if (col[u]) {
      if (ou++) printf(" ");
      printf("%d", u + 1);
    }
    puts("");
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}