Untitled

#include <iostream>
#define INF 10000000;
using namespace std;

int map[30][30];
int cnt[30];
int N,M;
int ans;

void clear(){
	for (int i = 0; i <= N+1; i++)
	{
		for (int j = 0; j <= N; j++)
		{
			map[i][j]=0;
		}
		
		cnt[i]=0;
	}

}

void backTrack(int u, int sum){
	if (u==1 && cnt[1] == 2 && cnt[2] ==1 )
	{
		if(sum < ans) ans=sum;
		return;
	}
	for (int i = 1; i <= map[u][0]; i++)
	{
		int v = map[u][i];
		//int cp=0;
		if (cnt[v] == 0)
		{
			/*cp =1;*/
			backTrack(v, sum +1);
		}
		else if (cnt[v] <2 && sum < ans)
		{
			cnt[v]++;
			backTrack(v,sum);
			cnt[v]--;
		}
		/*if (cnt[v] <2 && sum + cp < ans)
		{
			cnt[v] ++;
			backTrack(v, sum + cp);
			cnt[v] --;
		}*/

	}
}


int main(){
	freopen("input.txt","r",stdin);
	int T;
	cin>>T;
	for (int tc = 1; tc <= T ;tc++)
	{
		cin>>N>>M;
		clear();
		for (int i = 1; i <= M; i++)
		{
			int a, b;
			cin>>a>>b;
			map[a][0]++;
			map[a][map[a][0]] = b;
		}
		ans = INF;
		cnt[1] = 1;
		backTrack(1,1);
		cout<<ans<<endl;
	}

	return 0;
}