#include <bits/stdc++.h>
using namespace std;

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

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

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();
    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].emplace_back(v), h[v].emplace_back(u);
    }
    while (pq.size()) pq.pop();
    for (int i = 1; i <= n; 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; 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; 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), pq.push(make_pair(g[x].size(), x));
                for (int x : g[v]) if (x != u) g[x].erase(v), pq.push(make_pair(g[x].size(), x));
                break;
            }
        if (!Fl) vec.emplace_back(u);
    }

    for (int u : vec)
    {
        int pos1 = 0, pos2 = 0;
        for (int v : h[u])
            if (nxt[v])
            {
                if (!pos1) pos1 = pos2 = v;
                else pos2 = v;
            }
        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) cout << u << " "; cout << endl;
        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)
            {
                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 if (cnt1 > cnt2)
            {
                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);
                }
            }
            else
            {
                if (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 (reS.size() < reT.size())
        {
            swap(reS, reT);
            for (int u : dot) bel[u] = 3 - bel[u];
        }
        if (ansS.size() < ansT.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);
        }
    assert(ansS.size() == n / 2 || ansS.size() == (n + 1) / 2);
    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);

    int T; cin >> T;
    while (T--) work();
    return 0;
}