#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=1e6+10;
int T,n,m;
vector<int> g[N];
int cnt,fa[N],to[N],vis[N],pre[N];
int id,col[N];
queue<int> q;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int lca(int u,int v){
	++id,u=find(u),v=find(v);
	while(col[u]!=id){
		col[u]=id,u=find(pre[to[u]]);
		if(v)swap(u,v);
	}
	return u;
}
void blossom(int u,int v,int w){
	while(find(u)!=w){
		pre[u]=v,v=to[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];
	}
}
int aug(int s){
	if(n/2==cnt)return 0;
	for(int i=1;i<=n;i++)fa[i]=i,vis[i]=pre[i]=0;
	while(!q.empty())q.pop();
	q.push(s),vis[s]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int v:g[u]){
			if(find(u)==find(v)||vis[v]==2)continue;
			if(!vis[v]){
				vis[v]=2,pre[v]=u;
				if(!to[v]){
					for(int x=v,lst;x;x=lst)lst=to[pre[x]],to[x]=pre[x],to[pre[x]]=x;
					return 1;
				}
				vis[to[v]]=1,q.push(to[v]);
			}else{
				int w=lca(u,v);
				blossom(u,v,w),blossom(v,u,w);
			}
		}
	}
	return 0;
}
struct _2sat{
	int dfn[N],low[N],id,col[N],scc;
	struct edge{
		int v,nxt;
	}e[M];
	int hd[N],tot;
	void add(int u,int v){
		e[++tot]={v,hd[u]},hd[u]=tot;
	}
	int st[N],tp;bool ins[N];
	void tarjan(int u){
		low[u]=dfn[u]=++id;
		st[++tp]=u,ins[u]=1;
		for(int i=hd[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
			else if(ins[v])low[u]=min(low[u],low[v]);
		}
		if(low[u]==dfn[u]){
			++scc;
			do{
				col[u]=scc;
				u=st[tp--],ins[u]=0;
			}while(low[u]^dfn[u]);
		}
	}
	void clr(){
		for(int i=1;i<=n;i++){
			dfn[i]=low[i]=vis[i]=col[i]=0;
			hd[i]=0;
		}
		id=0,scc=0,tot=0;
	}
	bool solve(int x=0){
		clr();
		for(int u=1;u<=n;u++)if(u!=x){
			for(int v:g[u])if(v!=x){
				if(!to[u]&&!to[v])return 0;
				if(!to[u])add(to[v],v);
				else if(!to[v])add(to[u],u);
				else add(to[u],v),add(to[v],u);
			}
		}
		for(int i=1;i<=n;i++)if(to[i]&&!dfn[i])tarjan(i);
		for(int i=1;i<=n;i++)if(to[i]&&col[i]==col[to[i]]&&i!=x&&to[i]!=x)return 0;
		for(int i=1;i<=n;i++)if(to[i]){
			if(i==x||to[i]==x||col[i]<col[to[i]])vis[i]=1;
		}
		return 1;
	}
}s;
signed main(){
	scanf("%d",&T);
	for(;T--;){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			g[i].clear();
			to[i]=0;
		}
		cnt=0;
		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 i=1;i<=n;i++)if(!to[i])cnt+=aug(i);
		if(s.solve()){
			printf("%d\n",cnt);
			for(int i=1;i<=n;i++)if(vis[i])printf("%d ",i);puts("");
			continue;
		}
		bool flg=1;
		for(int i=1;i<=n;i++)if(s.solve(i)){
			flg=0;
			printf("%d\n",cnt+1);
			for(int j=1;j<=n;j++)if(vis[j]||j==i)printf("%d ",j);puts("");
			break;
		}
		if(flg)puts("not smol");
	}
}