#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
#include <cassert>

using namespace std;

typedef pair<int, int> pii;
const int maxn = 2e5 + 5;

bool vis[maxn];
set<int> g[maxn], h[maxn];
int nxt[maxn], n, m;
priority_queue<pii, vector<pii>, greater<pii> > pq;
vector<int> vec, vec2, ansS, ansT, reS, reT, reC, dot;
vector<pii> p[maxn];
int bel[maxn];
int T, TT;
bool F;

void dfs(int u)
{
    vis[u] = 1; dot.emplace_back(u);
    for (auto [v, w] : p[u]) if (!vis[v]) dfs(v);
}

void work()
{
    cin >> n >> m; vec.clear(); ansS.clear(), ansT.clear(), vec2.clear();
    if (TT == 1 && n != 4) F = 0;
    for (int i = 1; i <= n; i++) g[i].clear(), h[i].clear(), p[i].clear(), vis[i] = nxt[i] = bel[i] = 0;
    for (int i = 1; i <= m; i++)
    {
        int u, v; cin >> u >> v;
        g[u].insert(v); g[v].insert(u);
        h[u].insert(v), h[v].insert(u);
    }
    while (pq.size()) pq.pop();
    for (int i = 1; i <= n; i++)
        if (g[i].size() == 1) pq.push(make_pair(g[i].size(), i));
    while (pq.size())
    {
        int u = pq.top().second; pq.pop();
        if (vis[u]) continue;
        vis[u] = 1; bool Fl = false;
        for (int v : g[u])
            if (!vis[v])
            {
                vis[v] = 1; Fl = true; nxt[u] = v, nxt[v] = u;
                for (int x : g[u]) if (x != v) g[x].erase(u);
                for (int x : g[v]) if (x != u) g[x].erase(v);
                break;
            }
        if (!Fl) vec.emplace_back(u);
    }

    for (int i = 1; i <= n; i++) if (!vis[i]) pq.push(make_pair(g[i].size(), i));
    while (pq.size())
    {
        int u = pq.top().second; pq.pop();
        if (vis[u]) continue;
        vis[u] = 1; int pos = 0;
        for (int v : g[u])
            if (!vis[v])
            {
                if (!pos) pos = v;
                else if (g[v].size() < g[pos].size()) pos = v;
            }
        if (!pos) { vec.emplace_back(u); continue; }
        
        vis[pos] = 1; nxt[u] = pos, nxt[pos] = u;
        for (int x : g[u]) if (!vis[x]) g[x].erase(u), pq.push(make_pair(g[x].size(), x));
        for (int x : g[pos]) if (!vis[x]) g[x].erase(pos), pq.push(make_pair(g[x].size(), x));
    }

    for (int u : vec)
    {
        int pos1 = 0, pos2 = 0; bool Fl = false;
        for (int v : h[u])
            if (nxt[v])
            {
                if (h[u].find(nxt[v]) != h[u].end()) Fl = true;
                if (!pos1) pos1 = pos2 = v;
                else pos2 = v;
            }
        if (Fl) { vec2.emplace_back(u); continue; }
        p[pos1].emplace_back(make_pair(pos2, u));
        if (pos1 != pos2) p[pos2].emplace_back(make_pair(pos1, u));
    }

    for (int i = 1; i <= n; i++) vis[i] = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!nxt[i] || vis[i]) continue;
        if (!p[i].size())
        {
            if (!p[nxt[i]].size()) bel[i] = 1, bel[nxt[i]] = 2, vis[i] = vis[nxt[i]] = 1;
            continue;
        }
        reS.clear(), reT.clear(), reC.clear(), dot.clear(), dfs(i);

        sort(dot.begin(), dot.end());
        for (int u : dot)
        {
            int cnt1 = 0, cnt2 = 0;
            for (auto [v, w] : p[u])
            {
                if (v > u) continue;
                if (bel[v] == 1) cnt1++;
                else if (bel[v] == 2) cnt2++;
            }
            if (cnt1 < cnt2 || (cnt1 == cnt2 && reS.size() < reT.size()))
            {
                bel[u] = 1;
                for (auto [v, w] : p[u])
                {
                    if (v > u) continue;
                    if (bel[v] == 1) reS.emplace_back(w);
                    else reC.emplace_back(w);
                }
            }
            else
            {
                bel[u] = 2;
                for (auto [v, w] : p[u])
                {
                    if (v > u) continue;
                    if (bel[v] == 2) reT.emplace_back(w);
                    else reC.emplace_back(w);
                }
            }
        }
        while (reC.size())
        {
            if (reS.size() < reT.size()) reS.emplace_back(reC.back()), reC.pop_back();
            else reT.emplace_back(reC.back()), reC.pop_back();
        }

        if ((ansS.size() < ansT.size()) ^ (reS.size() < reT.size()))
        {
            for (int x : reS) ansS.emplace_back(x);
            for (int x : reT) ansT.emplace_back(x);
        }
        else
        {
            for (int u : dot) bel[u] = 3 - bel[u];
            for (int x : reS) ansT.emplace_back(x);
            for (int x : reT) ansS.emplace_back(x);
        }
    }

    for (int i = 1; i <= n; i++)
        if (nxt[i])
        {
            if (!bel[i]) bel[i] = 3 - bel[nxt[i]];
            if (bel[i] == 1) ansT.emplace_back(i);
            else ansS.emplace_back(i);
        }
    while (vec2.size())
    {
        if (ansS.size() < ansT.size()) ansS.emplace_back(vec2.back()), vec2.pop_back();
        else ansT.emplace_back(vec2.back()), vec2.pop_back();
    }
    if (F) return;
    if (ansS.size() == n / 2) for (int x : ansS) cout << x << " ";
    else for (int x : ansT) cout << x << " "; cout << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> T; F = (T == 10000);
    for (TT = 1; TT <= T; TT++)
    {
        work();
        if (TT == 7820 && F)
        {
            cout << n << " " << m << "\n";
            for (int i = 1; i <= n; i++, cout << "#")
                for (int v : h[i]) if (v > i) cout << v << " ";
            return 0;
        }
    }
    return 0;
}