#include<bits/stdc++.h>

using namespace std;
int n,m;
struct edge{
	int obj;
	int last;
}e[500005];
int head[1005],g;
void link(int u,int v){
	e[++g].obj=v;
	e[g].last=head[u];
	head[u]=g;
}
int fa[1005];
int vis[1005],pre[1005];
int match[1005];
queue<int>q;
int Find(int u){
	return (fa[u]==u?u:(fa[u]=Find(fa[u])));
}
int now;
int book[1005];
int lca(int u,int v){
	u=Find(u),v=Find(v);now++;
	while(book[u]!=now){
		book[u]=now;
		u=Find(pre[match[u]]);
		if(v)swap(u,v);
	}
	return u;
}
void blossom(int u,int v,int w){
	while(Find(u)!=w){
		pre[u]=v,v=match[u];
		if(vis[v]==2)vis[v]=1,q.push(v);
		if(Find(u)==u)fa[u]=w;
		if(Find(v)==v)fa[v]=w;
		u=pre[v];
	}
}
bool dfs(int u){
	for(int i=1;i<=n;i++)fa[i]=i,vis[i]=pre[i]=0;
	while(!q.empty())q.pop();
	q.push(u);vis[u]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=head[u];i;i=e[i].last){
			int v=e[i].obj;
			if(Find(u)==Find(v)||vis[v]==2)continue;
			if(!vis[v]){
				vis[v]=2;pre[v]=u;
				if(!match[v]){
					int now=v;
					while(now){
						int nxet=match[pre[now]];
						match[now]=pre[now];
						match[pre[now]]=now;
						now=nxet;
					}
					return true;
				}
				vis[match[v]]=1;q.push(match[v]);
			}
			else {
				int w=lca(u,v);
				blossom(u,v,w);
				blossom(v,u,w);
			}
		}
	}
	return false;
}
int su[500005],sv[500005];
namespace SAT{
	struct edge{
		int obj;
		int last;
	}e[4000005];
	int head[2005];
	int cnt;
	void link(int u,int v){
		e[++cnt].obj=v;
		e[cnt].last=head[u];
		head[u]=cnt;
	}
	int dfn[2005],low[2005];
	int g;
	int sta[2005],topf;
	int nid[2005];
	int id;
	void Tarjan(int u){
		dfn[u]=low[u]=++g;
		sta[++topf]=u;
		for(int i=head[u];i;i=e[i].last){
			int v=e[i].obj;
			if(!dfn[v]){
				Tarjan(v);
				low[u]=min(low[u],low[v]);
			}
			else {
				if(!nid[v]){
					low[u]=min(low[u],low[v]);
				}
			}
		}
		if(low[u]==dfn[u]){
			id++;
			while(1){
				int now=sta[topf];
				--topf;
				nid[now]=id;
				if(now==u)break;
			}
		}
	}
	bool Solve(int x){
		g=0;cnt=0;id=0;
		for(int i=1;i<=n;i++)head[i]=0,dfn[i]=low[i]=nid[i]=0;
		for(int i=1;i<=m;i++){
			if(su[i]==x||sv[i]==x||su[i]==match[x]||sv[i]==match[x]||match[su[i]]==sv[i])continue;
			if(!match[su[i]])link(match[sv[i]],sv[i]);
			else if(!match[sv[i]])link(match[su[i]],su[i]);
			else link(match[sv[i]],su[i]),link(match[su[i]],sv[i]);
		}
		for(int i=1;i<=n;i++){
			if(!match[i]||dfn[i])continue;
			Tarjan(i);
		}
		for(int i=1;i<=n;i++)
			if(match[i]&&i!=x&&i!=match[x]&&nid[i]==nid[match[i]])return false;
		return true;
	}
	void print(int x){
		for(int i=1;i<=n;i++)
			if(i==x||i==match[x]||nid[i]<nid[match[i]])printf("%d ",i);
	}
}
void Solve(){
	scanf("%d%d",&n,&m);
	g=0;
	for(int i=1;i<=n;i++)head[i]=vis[i]=pre[i]=match[i]=fa[i]=book[i]=0;
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		su[i]=u;sv[i]=v;
		link(u,v);link(v,u);
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		if(!match[i])ans+=dfs(i);
	for(int i=0;i<=n;i++)
		if(SAT::Solve(i)){
			printf("%d\n",ans+(i>0));
			SAT::print(i);
			putchar('\n');
			return;
		}
	puts("not smol");
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--)Solve();
	return 0;
}