#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(ll i=(a);i<=(b);++i)
#define Rep(i,a,b) for(ll i=(a);i>=(b);--i)
#define Yes printf("Yes\n")
#define No printf("No\n")
#define pb emplace_back
const ll N=1000+10;
using namespace std;
mt19937 rd(time(0));

ll n,m;
vector<ll>e[N];
ll a[N],b[N];
ll vis[N];
ll t[N][2];
ll ans;

void f(ll x){
	ans-=!t[x][vis[x]^1];
	for(ll y:e[x])ans-=!t[y][vis[y]^1],--t[y][vis[x]];
	vis[x]^=1;
	ans+=!t[x][vis[x]^1];
	for(ll y:e[x])++t[y][vis[x]],ans+=!t[y][vis[y]^1];
}

void mian(){
	
	scanf("%lld%lld",&n,&m);
	a[0]=b[0]=0;
	For(i,1,m){
		ll x,y;
		scanf("%lld%lld",&x,&y);
		e[x].pb(y),e[y].pb(x);
	}
	For(i,1,n){
		if(i&1)b[++b[0]]=i,vis[i]=1;
		else a[++a[0]]=i,vis[i]=0;
	}
	For(x,1,n){
		for(ll y:e[x])++t[x][vis[y]];
		ans+=!t[x][vis[x]^1];
	}
	while(ans){
		ll x=rd()%a[0]+1,y=rd()%b[0]+1;
		ll tmp=ans;
		f(a[x]),f(b[y]);
		if(tmp<ans)f(a[x]),f(b[y]);
		else swap(a[x],b[y]);
	}
	For(i,1,a[0])printf("%lld ",a[i]);
	printf("\n");
	For(i,1,n)e[i].clear(),t[i][0]=t[i][1]=0;
	
}
int main(){
	int T=1;
	scanf("%d",&T);
	while(T--)mian();
	return 0;
}