Untitled

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define MAX_SIZE 1000
#define INF 10000
using namespace std;

class Edge{
public:
	int x;
	int y;
};

Edge graph[200];
int visited[100];
int N, M;
int mi;

void DFS(int u, bool diquaTwo,int V){
	if(u == 1 && diquaTwo){
		if(mi > V){
			mi = V;
		}
		return;
	}
	if(V > mi){
		return;
	}
	++visited[u];
	for(int i = 0; i < M; ++i){
 		if(visited[graph[i].y] == 0 && u == graph[i].x){
			if(graph[i].y == 2){
				DFS(graph[i].y, true, V+1);
			}
			else{
				DFS(graph[i].y, diquaTwo, V+1);
			}
		}
		else if(visited[graph[i].y] == 1 && u == graph[i].x){
			DFS(graph[i].y, diquaTwo, V);
		}
	}
	--visited[u];
}

int main(){
	//freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc <= T; ++tc){
		cin >> N >> M;
		for(int i = 0; i < M; ++i){
			int x, y;
			cin >> graph[i].x >> graph[i].y;
		}
		for(int i = 0; i < N; ++i){
			visited[i] = 0;
		}
		mi = INF;
		DFS(1, false, 1);
		cout << mi << endl;
	}

	return 0;
}