Untitled

#include<iostream>
using namespace std;
int N,M;// N: so luong dinh, M so duong di, 
int dske[21][21];
int index[21];
int ans;
int visit[21];
int flag;
int minn;

void input(){
	int a,b;
	cin>>N>>M;
	for(int i = 1; i <= N; i++){
		visit[i] = 0;
		index[i] = 0;
	}
	for(int i=0;i<M;i++){
		cin>>a>>b;
		dske[a][index[a]]=b;
		index[a]++;
	}
	
	
}

void backTrack2(int dinh, int sum)
{
	if(sum > ans)
		return;
	if(dinh == 1){
		if(sum < ans)
			ans = sum;
		return;
	}
	for(int i = 0; i < index[dinh]; i++){
		if(visit[dske[dinh][i]] == 0){
			visit[dske[dinh][i]] = 1;
			backTrack2(dske[dinh][i], sum + 1);
			visit[dske[dinh][i]] = 0;
		}
		if(visit[dske[dinh][i]] == 1){
			visit[dske[dinh][i]] = 2;
			backTrack2(dske[dinh][i], sum);
			visit[dske[dinh][i]] = 1;
		}
	}
}

void backTrack1(int dinh, int sum)
{
	if(sum > ans)
		return;
	if(dinh == 2){
		backTrack2( 2, sum);
		return;
	}
	for(int i = 0; i < index[dinh]; i++){
		if(visit[dske[dinh][i]] == 0){
			visit[dske[dinh][i]] = 1;
			backTrack1(dske[dinh][i], sum + 1);
			visit[dske[dinh][i]] = 0;
		}
	}
}

int main()
{
	freopen("input.txt" , "r", stdin);
	int T; 
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		input();
		ans = 100000;
		visit[1] = 1;
		backTrack1(1,1);
		cout  << ans << endl;
	}
	return 0;
}

//input
2

6 7

1 3

3 4

4 5

5 1

4 2

2 6

6 3

9 11

1 3

3 4

4 2

2 5

5 3

3 6

6 1

2 7

7 8

8 9

9 1