#include<bits/stdc++.h>
using namespace std;
namespace sat {
const int MAXN=505;
vector <int> E[MAXN];
int dfn[MAXN],low[MAXN],col[MAXN],stk[MAXN],dc,sc,tp,n;
bool ins[MAXN],ans[MAXN];
void init() {
	dc=sc=tp=0;
	for(int i=1;i<=2*n;++i) dfn[i]=low[i]=col[i]=stk[i]=ans[i]=ins[i]=0,E[i].clear();
}
void link(int u,int x,int v,int y) { E[u+x*n].push_back(v+y*n); }
void tarjan(int u) {
	dfn[u]=low[u]=++dc,stk[++tp]=u,ins[u]=1;
	for(int v:E[u]) {
		if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
		else if(ins[v]) low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u]) {
		int k; ++sc;
		do k=stk[tp--],col[k]=sc,ins[k]=0;
		while(k^u);
	}
}
bool solve() {
	for(int i=1;i<=2*n;++i) if(!dfn[i]) tarjan(i);
	for(int i=1;i<=n;++i) if(col[i]==col[i+n]) return false;
	for(int i=1;i<=n;++i) ans[i]=col[i+n]<col[i];
	return true;
}
}
const int MAXN=505;
vector <int> G[MAXN];
int q[MAXN],vis[MAXN],p[MAXN],c[MAXN],e[MAXN][2];
mt19937 rnd(time(0));
bool dfs(int u,int z) {
	if(vis[u]==z) return false;
	vis[u]=z,shuffle(G[u].begin(),G[u].end(),rnd);
	for(int v:G[u]) {
		int w=q[v];
		q[w]=0,q[u]=v,q[v]=u;
		if(!w||dfs(w,z)) return true;
		q[w]=v,q[v]=w,q[u]=0;
	}
	return false;
}
void solve() {
	int n,m,z=0;
	scanf("%d%d",&n,&m);
	vector <int> o;
	for(int i=1;i<=n;++i) G[i].clear(),vis[i]=q[i]=p[i]=c[i]=0,o.push_back(i);
	for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
	for(int T=0;T<10;++T) {
		shuffle(o.begin(),o.end(),rnd);
		for(int u:o) if(!q[u]) dfs(u,++z);
	}
	int s=0;
	for(int i=1;i<=n;++i) if(q[i]>i) {
		++s,p[i]=p[q[i]]=s,c[i]=0,c[q[i]]=1,e[s][0]=i,e[s][1]=q[i];
	}
	sat::n=s,sat::init();
	for(int u=1;u<=n;++u) for(int v:G[u]) if(u<v) {
		if(p[u]&&p[v]) {
			if(p[u]==p[v]) continue;
			sat::link(p[u],c[u]^1,p[v],c[v]);
			sat::link(p[v],c[v]^1,p[u],c[u]);
		} else if(p[u]) {
			sat::link(p[u],c[u]^1,p[u],c[u]);
		} else if(p[v]) {
			sat::link(p[v],c[v]^1,p[v],c[v]);
		}
	}
	if(sat::solve()) {
		printf("%d\n",s);
		for(int i=1;i<=s;++i) printf("%d ",e[i][sat::ans[i]]);
		puts(""); return ;
	}
	for(int x=1;x<=n;++x) if(!p[x]) {
		sat::n=s,sat::init();
		for(int u=1;u<=n;++u) for(int v:G[u]) if(u<v&&u!=x&&v!=x) {
			if(p[u]&&p[v]) {
				if(p[u]==p[v]) continue;
				sat::link(p[u],c[u]^1,p[v],c[v]);
				sat::link(p[v],c[v]^1,p[u],c[u]);
			} else if(p[u]) {
				sat::link(p[u],c[u]^1,p[u],c[u]);
			} else if(p[v]) {
				sat::link(p[v],c[v]^1,p[v],c[v]);
			}
		}
		if(sat::solve()) {
			printf("%d\n",s+1);
			for(int i=1;i<=s;++i) printf("%d ",e[i][sat::ans[i]]);
			printf("%d\n",x); return ;
		}
	}
	puts("smol");
}
signed main() {
	int T; scanf("%d",&T);
	while(T--) solve();
	return 0;
}