#include<bits/stdc++.h>
using namespace std;
int n,m,vis[1111],mt[1111],M,u[200005],v[200005],cnt,dfn[1111],low[1111],ins[1111],scnt,op[1111];
vector<int>e[1111];
stack<int>s;
mt19937 rd(1145);
bool dfs(int x){
	shuffle(e[x].begin(),e[x].end(),rd);
	vis[x]=1;
	for(int i:e[x]) if(!mt[i]) return mt[x]=i,mt[i]=x,1;
	for(int i:e[x]){
		int to=mt[i];
		if(vis[i]||vis[to]) continue;
		mt[x]=i,mt[i]=x,mt[to]=0;
		if(dfs(to)) return 1;
		mt[x]=0,mt[i]=to,mt[to]=i;
	}
	return 0;
}
void adde(int x,int y){
//	cout<<x<<" "<<y<<endl;
	e[x].push_back(y);
}
void trj(int x){
	s.push(x);
	vis[x]=1;
	dfn[x]=low[x]=++cnt;
//	cout<<"+ "<<x<<" "<<dfn[x]<<" "<<low[x]<<endl;
	for(int i:e[x]){
		if(!dfn[i]) trj(i),low[x]=min(low[x],low[i]);
		else if(vis[i]) low[x]=min(low[x],dfn[i]); 
	}
//	cout<<"- "<<x<<" "<<dfn[x]<<" "<<low[x]<<endl;
	if(low[x]==dfn[x]){
//		cout<<scnt+1<<" : "<<x<<" ";
		for(int o=ins[x]=++scnt;(o=s.top())!=x;s.pop()) ins[o]=scnt,vis[o]=0;//,cout<<o<<" ";
//		cout<<endl;
		vis[x]=0;
		s.pop();
	}
}
void bd(int x){
	for(int i=1;i<=n+n;i++) e[i].clear();
	for(int i=1;i<=n;i++) if(!mt[i]) i^x?adde(i+n,i):adde(i,i+n);
	for(int i=1;i<=m;i++) adde(u[i],v[i]+n),adde(v[i],u[i]+n);
	for(int i=1;i<=n;i++) if(mt[i]) adde(i+n,mt[i]);
}
bool chk(){
	cnt=scnt=0;
	for(int i=1;i<=n+n;i++) dfn[i]=vis[i]=0;
	for(int i=1;i<=n+n;i++) if(!dfn[i]) trj(i);
//	for(int i=1;i<=n+n;i++) cout<<ins[i]<<" \n"[i==n+n];
	for(int i=1;i<=n;i++) if(ins[i]==ins[i+n]) return 0;
	return 1;
}
void out(){
	for(int i=1;i<=n;i++) op[i]=ins[i]>ins[i+n];
	vector<int>c;
	for(int i=1;i<=n;i++) if(op[i]) c.push_back(i);
	cout<<c.size()<<"\n";
	for(int i:c) cout<<i<<" ";
	cout<<endl;
}
void doing(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) e[i].clear();
	for(int i=1;i<=m;i++){
		scanf("%d %d",&u[i],&v[i]);
		adde(u[i],v[i]);
		adde(v[i],u[i]);
	}
	int cnt=M=0;
	while(cnt<=n*3+2&&M<n/2){
		for(int j=1;j<=n;j++){
			if(!mt[j]){
				memset(vis,0,sizeof(vis));
				M+=dfs(j);
				cnt++;
			}
		}
	}
	bd(0);
	if(chk()) return out();
	for(int i=1;i<=n;i++){
		if(!mt[i]){
//			cout<<i<<"!!!\n";
			bd(i);
			if(chk()) return out();
		}
	}
	printf("not smol\n");
}
int main(){
	int T;
	cin>>T;
	while(T--) doing();
}