#include <bits/stdc++.h>
using namespace std;
int Qread()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	return x;	
}
vector<int> ed[510];
void add_edge(int u,int v)
{
	ed[u].push_back(v);
	ed[v].push_back(u);
}
int n,m,M;
int pp[510],pre[510],col[510],fa[510];
int get_fa(int a){return a==fa[a]?a:fa[a]=get_fa(fa[a]);}
void rev(int a){if(a) rev(pp[pre[a]]),pp[pre[a]]=a,pp[a]=pre[a];}
queue<int> Q;

int dfn[510],zsh;
int lca(int x,int y)
{
	for(zsh++;;x=pre[pp[x]],swap(x,y))
		if(dfn[x=get_fa(x)]==zsh) return x;
		else if(x) dfn[x]=zsh;	
}
void shrink(int x,int y,int p)
{
	while(get_fa(x)!=p)
	{
		pre[x]=y,y=pp[x],fa[x]=fa[y]=p;
		if(col[y]==2) col[y]=1,Q.push(y);
		x=pre[y];	
	}
}
int u,p;
int bfs(int s)
{
	for(int i=1;i<=n;i++) pre[i]=col[i]=0,fa[i]=i;
	queue<int>().swap(Q);Q.push(s);col[s]=1;
	while(!Q.empty())
	{
		u=Q.front();Q.pop();
		for(int v:ed[u])
		{
			if(col[v]==1)
				p=lca(u,v),shrink(u,v,p),shrink(v,u,p);
			else if(!col[v])
			{
				col[v]=2,pre[v]=u;
				if(!pp[v]) return rev(v),1;
				else col[pp[v]]=1,Q.push(pp[v]);
			}
		}
	}
	return 0;
}

namespace two_SAT{
	vector<int> ed[510];
	void add_edge(int u,int v){ed[u].push_back(v);}
	
	int stk[510],top;
	bool vis[510],instk[510];
	int dfn[510],low[510],ind,bel[510],scc_cnt;
	
	void Tarjan(int a)
	{
		dfn[a]=low[a]=++ind;
		vis[a]=instk[a]=true;
		stk[++top]=a;
		for(int v:ed[a])
		{
			if(vis[v])
			{
				if(instk[v]) low[a]=min(low[a],dfn[v]);
			}
			else
			{
				Tarjan(v);
				if(instk[v]) low[a]=min(low[a],low[v]);
			}
		}
		if(low[a]==dfn[a])
		{
			++scc_cnt;
			while(top&&stk[top+1]!=a)
			{
				bel[stk[top]]=scc_cnt;
				instk[stk[top]]=false;
				top--;
			}
		}
	}
	vector<int> edn[510];
	int rd[510],tpx[510];
	bool typ[510];
	
	void reset(int n)
	{
		memset(vis,0,n+1);
		for(int i=1;i<=n;i++) vector<int>().swap(ed[i]);
		for(int i=1;i<=scc_cnt;i++) vector<int>().swap(edn[i]);
		scc_cnt=ind=0;
	}
	
	queue<int> Q;int rea;
	bool solve(int n,int n2)
	{
		for(int i=1;i<=n;i++)
			if(!vis[i]) Tarjan(i);
		for(int i=1;i<=n;i++) for(int v:ed[i])
			if(bel[i]!=bel[v]) edn[bel[i]].push_back(bel[v]),rd[bel[v]]++;
		for(int i=1;i<=scc_cnt;i++)
			if(!rd[i]) Q.push(i);
		ind=0;
		while(!Q.empty())
		{
			rea=Q.front();Q.pop();
			tpx[rea]=++ind;
			for(int v:ed[rea]) if(!(--rd[v]))
				Q.push(v);
		}
		for(int i=1;i<=n2;i++)
		{
			if(bel[i]==bel[i+n2]) return false;
			else if(tpx[bel[i]]<tpx[bel[i+n2]]) typ[i]=2;
			else typ[i]=1;
		}
		return true;
	}
}
int eu[124760],ev[124760];
int ind[310][2],vs[510],opvs[510];int fl;
void solve()
{
	M=fl=0;for(int i=1;i<=n;i++) vector<int>().swap(ed[i]),pp[i]=0;
	memset(vs,0,(n+1)<<2),memset(opvs,0,(n+1)<<2);
	
	n=Qread(),m=Qread();
	for(int i=1;i<=m;i++) add_edge(eu[i]=Qread(),ev[i]=Qread());
		
	if(m==0) return printf("0\n\n"),void();
	for(int i=1;i<=n;i++) if(!pp[i])
		M+=bfs(i);
	
	for(int i=1;i<=n;i++) if(!vs[i]&&pp[i])
		++fl,ind[fl][0]=i,ind[fl][1]=pp[i],vs[i]=opvs[pp[i]]=fl,opvs[i]=vs[pp[i]]=M+fl;
	
	//check if C=M is able
	two_SAT::reset(M<<1);
	for(int i=1;i<=m;i++)
	{
		if(vs[eu[i]]&&vs[ev[i]])
		{
			two_SAT::add_edge(opvs[eu[i]],vs[ev[i]]);
			two_SAT::add_edge(opvs[ev[i]],vs[eu[i]]);
		}
		else if(vs[eu[i]]) two_SAT::add_edge(opvs[eu[i]],vs[eu[i]]);
		else if(vs[ev[i]]) two_SAT::add_edge(opvs[ev[i]],vs[ev[i]]);
	}
	if(two_SAT::solve(M<<1,M))
	{
		printf("%d\n",M);
		for(int i=1;i<=M;i++)
			printf("%d%c",ind[i][two_SAT::typ[i]-1]," \n"[i==M]);
		return;
	}
	//check if C=M+1 is able
	for(int rea=1;rea<=n;rea++) if(!pp[rea])
	{
		two_SAT::reset(M<<1);
		for(int i=1;i<=m;i++)
		{
			if(eu[i]==rea||ev[i]==rea) continue;
			if(vs[eu[i]]&&vs[ev[i]])
			{
				two_SAT::add_edge(opvs[eu[i]],vs[ev[i]]);
				two_SAT::add_edge(opvs[ev[i]],vs[eu[i]]);
			}
			else if(vs[eu[i]]) two_SAT::add_edge(opvs[eu[i]],vs[eu[i]]);
			else if(vs[ev[i]]) two_SAT::add_edge(opvs[ev[i]],vs[ev[i]]);
		}
		if(two_SAT::solve(M<<1,M))
		{
			printf("%d\n",M+1);
			for(int i=1;i<=M;i++)
				printf("%d ",ind[i][two_SAT::typ[i]-1]);
			printf("%d\n",rea);
			return;
		}
	}
	else if(vs[rea]<=M)
	{
		two_SAT::reset(M<<1);
		for(int i=1;i<=m;i++)
		{
			if(eu[i]==rea||ev[i]==rea||eu[i]==pp[rea]||ev[i]==pp[rea]) continue;
			if(vs[eu[i]]&&vs[ev[i]])
			{
				two_SAT::add_edge(opvs[eu[i]],vs[ev[i]]);
				two_SAT::add_edge(opvs[ev[i]],vs[eu[i]]);
			}
			else if(vs[eu[i]]) two_SAT::add_edge(opvs[eu[i]],vs[eu[i]]);
			else if(vs[ev[i]]) two_SAT::add_edge(opvs[ev[i]],vs[ev[i]]);
		}
		two_SAT::add_edge(vs[rea],M+vs[rea]);
		if(two_SAT::solve(M<<1,M))
		{
			printf("%d\n",M+1);
			for(int i=1;i<=M;i++)
				printf("%d ",ind[i][two_SAT::typ[i]-1]);
			printf("%d\n",rea);
			return;
		}
	}
	printf("not smol\n");
}
int main()
{
	int T=Qread();
	while(T--) solve();
	return 0;
}