//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
const ll mod=1e9+7;
const ll base=10;
ll ksm(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
const ll inv10=ksm(10,mod-2);
int u[1001000],v[1001000];
int n,m;
vector<int> G[500500],rG[500500];
int nxt[500500],lst[500500];
int deg[500500],ind[500500];
int vis[500500];
ll pw[500500];
void dfs(int u)
{
	if(~nxt[u]) return ;
	if(deg[u]>1) return ;
	vis[u]=1;
	int v=-1;
	for(auto v:rG[u])
		deg[v]--;
	for(auto w:G[u])
		if(!vis[w])
			v=w;
	if(v==-1) return ;
	if(~lst[v]) return ;
	nxt[u]=v;
	lst[v]=u;
	dfs(v);
}
ll get(int st)
{
	memset(nxt,-1,sizeof(int)*(n+10));
	memset(lst,-1,sizeof(int)*(n+10));
	memset(vis,0,sizeof(int)*(n+10));
	for(int i=1;i<=n;i++)
		deg[i]=sz(G[i]);
	dfs(st);
	ll ret=0;
	for(int i=0;i<n;i++)
	{
		ret=(ret*10+st)%mod;
		st=nxt[st];
	}
	return ret;
}
int delta[500500];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	pw[0]=1;
	for(int i=1;i<500500;i++)
		pw[i]=pw[i-1]*base%mod;
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		for(int i=1;i<=m;i++)
			cin>>u[i]>>v[i];
		for(int i=1;i<=n;i++)
		{
			G[i].clear();
			rG[i].clear();
		}
		for(int i=1;i<=m;i++)
		{
			G[u[i]].pb(v[i]);
			rG[v[i]].pb(u[i]);
		}
		for(int i=1;i<=n;i++)
		{
			srt(G[i]);
			uni(G[i]);
			srt(rG[i]);
			uni(rG[i]);
			deg[i]=sz(G[i]);
		}
		memset(nxt,-1,sizeof(int)*(n+10));
		memset(lst,-1,sizeof(int)*(n+10));
		memset(vis,0,sizeof(int)*(n+10));
		memset(delta,0,sizeof(int)*(n+10));
		for(int i=1;i<=n;i++)
			if(deg[i]==1)
				dfs(i);
		int cnt=0;
		for(int i=1;i<=n;i++)
			if(nxt[i]==-1)
				cnt++;
		if(cnt>1)
			cout<<"0\n";
		else
		{
			vector<int> ord;
			int cur=1;
			for(int i=1;i<=n;i++)
				if(lst[i]==-1)
					cur=i;
			ord.pb(cur);
			while(sz(ord)<n)
				ord.pb(nxt[ord.back()]);
			for(int i=0;i<n;i++)
				ind[ord[i]]=i;
			int st=-1;
			int bck=n;
			for(auto v:G[ord.back()])
				bck=min(bck,ind[v]);
			if(bck!=n)
			{
				vector<int> vec;
				for(int i=bck+1;i<n;i++)
				{
					bool flag=0;
					for(auto j:G[ord[i]])
						if(ind[j]<bck)
							flag=1;
					if(flag)
						vec.pb(i);
				}
				if(sz(vec)==1)
					st=ord[vec[0]+1];
				else if(!sz(vec))
					st=ord[bck+1];
			}
			if(~st)
			{
				cout<<"2\n";
				if(ord[0]<st)
					cout<<get(ord[0])<<" "<<get(st)<<'\n';
				else
					cout<<get(st)<<" "<<get(ord[0])<<'\n';
			}
			else
			{
				cout<<"1\n";
				cout<<get(ord[0])<<'\n';
			}
		}
	}
	return 0;
}