// Author: kyEEcccccc

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
using ULL = unsigned long long;

#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)

constexpr int N = 200005, M = 500005;

int n, m;
set<int> to[N];
int tot_lf[N];

bool vis[N];
vector<int> pt1, pt2, pt3;
vector<pair<int, int>> nto[N];

int co[N];
vector<int> ans1, ans2;
int dlt;

void dfs(int u)
{
	if (tot_lf[u] == 2) pt1.push_back(u);
	else if (to[u].size() == 2) pt2.push_back(u);
	else pt3.push_back(u);
	vis[u] = true;
	for (auto v : to[u])
	{
		if (vis[v]) continue;
		dfs(v);
	}
}

void solve(int s)
{
	pt1.clear(), pt2.clear(), pt3.clear();
	dfs(s);
	
	if (pt1.empty() && pt2.empty())
	{
		assert(pt3.size() == 2);
		ans1.push_back(*pt3.begin());
		ans2.push_back(*next(pt3.begin()));
		return;
	}

	for (auto u : pt2)
	{
		nto[*to[u].begin()].push_back({*next(to[u].begin()), u});
		nto[*next(to[u].begin())].push_back({*to[u].begin(), u});
	}

	for (auto u : pt1)
	{
		vector<int> p1, p2;
		for (auto vi : nto[u])
		{
			if (co[vi.first] == 1) p1.push_back(vi.second);
			if (co[vi.first] == 2) p2.push_back(vi.second);
		}
		if (dlt + (int)p1.size() + 1 <= (int)p2.size() + 1)
		{
			co[u] = 1;
			ans1.push_back(u);
			dlt += 1;
			for (auto v : p1) ans2.push_back(v), ++dlt;
			for (auto v : p2)
			{
				if (dlt > 0)
				{
					ans1.push_back(v);
					--dlt;
				}
				else
				{
					ans2.push_back(u);
					++dlt;
				}
			}
		}
		else
		{
			assert(-(dlt - (int)p2.size() - 1) <= (int)p1.size() + 1);
			co[u] = 2;
			ans2.push_back(u);
			dlt -= 1;
			for (auto v : p2) ans1.push_back(v), --dlt;
			for (auto v : p1)
			{
				if (dlt > 0)
				{
					ans1.push_back(v);
					--dlt;
				}
				else
				{
					ans2.push_back(u);
					++dlt;
				}
			}
		}
	}

	for (auto u : pt3)
	{
		if (co[*to[u].begin()] == 1) ans2.push_back(u);
		else ans1.push_back(u);
	}
}

void work(void)
{
	cin >> n >> m;

	F(i, 1, n)
	{
		to[i].clear();
		tot_lf[i] = 0;
		vis[i] = false;
		nto[i].clear();
		co[i] = 0;
	}

	F(i, 1, m)
	{
		int u, v; cin >> u >> v;
		to[u].insert(v), to[v].insert(u);
	}

	F(i, 1, n)
	{
		if (to[i].size() != 1) continue;
		tot_lf[*to[i].begin()] += 1;
	}
	F(u, 1, n)
	{
		set<int> tmp = to[u];
		for (auto v : tmp)
		{
			if (to[v].size() == 1 || to[u].size() == 1) continue;
			int t1 = 0, t2 = 0;
			if (to[v].size() == 2)
			{
				if (*to[v].begin() == u) t1 = *next(to[v].begin());
				else t1 = *to[v].begin();
			}
			if (to[u].size() == 2)
			{
				if (*to[u].begin() == v) t2 = *next(to[u].begin());
				else t2 = *to[u].begin();
			}
			bool ok;
			if (t1 == t2)
			{
				if (tot_lf[t1] > 0) ok = false;
				else ok = true;
			}
			else
			{
				if (tot_lf[t1] > 1 || tot_lf[t2] > 1) ok = false;
				else ok = true;
			}
			if (ok) to[u].erase(v), to[v].erase(u), ++tot_lf[t1], ++tot_lf[t2];
		}
	}

	ans1.clear();
	ans2.clear();
	dlt = 0;
	F(i, 1, n) if (!vis[i]) solve(i);

	if (dlt == -1) swap(ans1, ans2);
	for (auto x : ans1) cout << x << ' ';
	cout << '\n';
}

signed main(void)
{
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(nullptr);

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