#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x;i<=y;i++)
#define df(i,x,y) for(int i=x;i>=y;i--)
#define int long long
#define pb push_back
using namespace std;
const int N=1.1e6;
int n,a[N],a1[N],c[N],l,l1,x,y,cs,t1,m,t,v[N][2];
vector<int>b[N];
mt19937 rd(time(0));
void cg(int i)
{
	t-=(!v[i][c[i]^1]);
	for(int u:b[i])t-=(!v[u][c[u]^1]),--v[u][c[i]];
	c[i]^=1;
	t+=(!v[i][c[i]^1]);
	for(int u:b[i])++v[u][c[i]],t+=(!v[u][c[u]^1]);
}
signed main()
{
	scanf("%lld",&cs);
	while(cs--)
	{
		scanf("%lld%lld",&n,&m);
		l=l1=0;
		f(i,1,n)b[i].clear(),v[i][0]=v[i][1]=0;
		f(i,1,m)scanf("%lld%lld",&x,&y),b[x].pb(y),b[y].pb(x);
		f(i,1,n)if(i&1)a1[++l1]=i,c[i]=1;else a[++l]=i,c[i]=0;
		f(i,1,n)for(int u:b[i])++v[i][c[u]];
		f(i,1,n)t+=(!v[i][c[i]^1]);
		while(t)
		{
			x=rd()%l+1;y=rd()%l1+1;
			t1=t;
			cg(a[x]),cg(a1[y]);
			if(t1<t)cg(a[x]),cg(a1[y]);
			else swap(a[x],a1[y]);
		}
		f(i,1,l)cout<<a[i]<<' ';
		cout<<'\n';
	}
	return 0;
}