Untitled

#include <iostream>
#define N 1001
#define oo 2000000009
using namespace std;
int n,m;
int ke[N][N];
int dd[N];
int cnt[N];
int kc[N];
int ans;
void doc()
{
	ans=oo;
	int u,v;
	cin>>n>>m;
	for(int i=1;i<=n;i++)ke[i][0]=0,cnt[i]=0;
	
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v;
		ke[u][0]++;
		ke[u][ke[u][0]]=v;
	}
}

void backtrack(int u, int sum)
{
	//cout<<u<<" "<<sum<<"\n";
	if(u==1&&cnt[1]==2&&cnt[2]==1)
	{
		
		if(sum<ans)ans=sum;
		return;
	}
	for(int i=1;i<=ke[u][0];i++)
	{
		int v=ke[u][i];
		int cp=0;
		if(cnt[v]==0)cp=1;
		if(cnt[v]<2&&sum+cp<ans)
		{
			cnt[v]++;
			backtrack(v,sum+cp);
			cnt[v]--;
		}
	}
	
}
int main()
{
	//freopen("input.txt","r",stdin);
	int TC;
	cin>>TC;
	for(int tc=1;tc<=TC;tc++)
	{
		doc();
		cnt[1]=1;
		backtrack(1,1);
		cout<<ans<<"\n";
	}
	return 0;
}