#include <bits/stdc++.h>
#define db double
#define il inline
#define re register
#define ll long long
#define ui unsigned
#define ull ui ll
#define i128 __int128
#define pii pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define mems(v, x) memset(v, x, sizeof(v))
#define memc(a, b) memcpy(a, b, sizeof(a))
#define FOR(i, L, R) for(re int i = (L); i <= (R); ++i)
#define ROF(i, R, L) for(re int i = (R); i >= (L); --i)
#define LS i << 1, l, mid
#define RS i << 1 | 1, mid + 1, r
#define popc(x) __builtin_popcount(x)
using namespace std;
#define N 200005
#define M 500005
#define P 1000000007
il int add(int x, int y) {return x + y < P ? x + y : x + y - P;}
il void addr(int &x, int y) {(x += y) >= P && (x -= P);}
il int qpow(int p, int n = P - 2) {
  int s = 1;
  while(n) {
    if(n & 1) s = 1ll * s * p % P;
    p = 1ll * p * p % P, n >>= 1;
  }
  return s;
}
il void chkmin(int &x, int y) {(x > y) && (x = y);}
il void chkmax(int &x, int y) {(x < y) && (x = y);}
mt19937 rnd(114514);
int n, m;
set<int> e[N]; int cnt[N];
bool us[N]; int be[N], det;
vector<int> A, B, C;
vector<pii> tr[N];
il void dfs(int x) {
  if(us[x]) return ; us[x] = 1;
  if(cnt[x] == 2) A.eb(x);
  else if(SZ(e[x]) == 2) B.eb(x);
  else C.eb(x); for(auto y : e[x]) dfs(y);
}
il void work(int x) {
  dfs(x);
  if(A.empty() && B.empty()) {
    int a = C[0], b = C[1];
    be[a] = 1, be[b] = 2; return ;
  }
  for(auto x : B) {
    int a = *e[x].begin(), b = *e[x].rbegin();
    tr[a].eb(b, x), tr[b].eb(a, x);
  }
  for(auto x : A) {
    vector<int> s, t;
    for(auto [y, p] : tr[x]) {
      if(be[y] == 1) s.eb(p);
      if(be[y] == 2) t.eb(p);
    }
    if(abs(det + 1 - 2 - SZ(s)) <= SZ(t)) {
      be[x] = 1, --det;
      for(auto p : s) be[p] = 2, --det;
      for(auto p : t) {
        if(det > 0) be[p] = 2, --det;
        else be[p] = 1, ++det;
      }
    }
    else {
      be[x] = 2, ++det;
      for(auto p : t) be[p] = 1, ++det;
      for(auto p : s) {
        if(det > 0) be[p] = 2, --det;
        else be[p] = 1, ++det;
      }
    }
  }
  for(auto x : C) be[x] = 3 - be[*e[x].begin()];
}
il void WORK() {
  cin >> n >> m;
  FOR(i, 1, n) set<int>().swap(e[i]), vector<pii>().swap(tr[i]), be[i] = cnt[i] = us[i] = 0;
  FOR(i, 1, m) {int u, v; cin >> u >> v, e[u].insert(v), e[v].insert(u);}
  FOR(i, 1, n) if(SZ(e[i]) == 1) for(auto x : e[i]) ++cnt[x];
  FOR(u, 1, n) {
    set<int> nbr = e[u];
    for(auto v : nbr) {
      if(SZ(e[u]) == 1 || SZ(e[v]) == 1) continue; int a = 0, b = 0;
      if(SZ(e[u]) == 2) for(auto x : e[u]) if(x != v) a = x;
      if(SZ(e[v]) == 2) for(auto x : e[v]) if(x != u) b = x;
      if(max(cnt[a], cnt[b]) <= 1 - (a == b)) {
        e[u].erase(v), e[v].erase(u);
        if(a) ++cnt[a]; if(b) ++cnt[b];
      }
    }
  }
  // FOR(u, 1, n) {for(auto v : e[u]) cout << u << " " << v << "\n";}
  det = 0; FOR(i, 1, n) if(!be[i]) work(i); int id = 1 + (det > 0);
  FOR(i, 1, n) if(be[i] == id) cout << i << " "; cout << "\n";
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int T; cin >> T;
  while(T--) WORK();
  cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
  return 0;
}