Untitled

#include<iostream>

using namespace std;

int N, M;
int visited1[25];
int visited2[25];
int map[25][25];
int result = 9999999;

int main() {
	int T;

	//freopen("input.txt", "r", stdin);

	cin >> T;
	for(int tc = 1; tc <= T; tc++) {
		resetData();
		takeInput();

		visited1[1] = 1;
		dfs1(1, 1);

		cout << result << endl;

	}
	return 0;
}

void resetData(){
	result = 9999999;
	for(int i = 0; i < 25; i++){
		visited2[i] = visited1[i] = 0;
		for(int j = 0; j < 25; j++){
			map[i][j] = 0;
		}	
	}
}

void takeInput(){
	cin >> N >> M;
	for(int i = 0; i < M; i++){
		int a, b;
		cin >> a >> b;
		map[a][b] = 1;
	}
}


void dfs2(int root, int cnt){
	if(cnt > result)
		return;

	if(root == 1){
		if(result > cnt) 
			result = cnt;
		return;
	}

	for(int i = 1; i <= N; i++){
		if(visited2[i] == 0 && map[root][i] == 1){
			visited2[i] = 1;
			if(visited1[i] == 0) {
				dfs2(i, cnt+1);
			}else {
				dfs2(i, cnt);
			}
			visited2[i] = 0;
		}
	}
}

void dfs1(int root, int cnt){
	if(cnt > result)
		return;

	if(root == 2){
		visited2[2] = 1;
		dfs2(2, cnt);
		return;
	}

	for(int i = 1; i <= N; i++){
		if(visited1[i] == 0 && map[root][i] == 1){
			visited1[i] = 1;
			dfs1(i, cnt+1);
			visited1[i] = 0;
		}
	}
}