Untitled

#include <iostream>
using namespace std;
int n,m;
int kq;
int duongdi[21][21];
int visit1[21];
int visit2[21];
int kq1,kq2;
void go1(int st, int dem){
	if(visit1[st] > 1) return;
	if(visit1[2] == 1){
		if(dem < kq1) kq1 = dem;
		return;
	}
	for(int i = 1; i <= n; i++){
		if(duongdi[st][i] == 1){
			visit1[i]++;
			go1(i, dem + 1);
		    visit1[i]--;
		}
	}
}
void go2(int st, int dem){
	if(visit2[st] > 1 ) return;
	if(visit2[1] == 1){
		if(dem < kq2) kq2 = dem;
		return;
	}
	for(int i = 1; i <= n; i++){
		if(duongdi[st][i] == 1){
			visit2[i]++;
			go2(i, dem + 1);
			visit2[i]--;
		}
	}
}
int main(){
	freopen("input.txt","r",stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> n >> m;
		for(int i = 1; i<= n; i++){
			visit1[i] = 0;
			visit2[i] = 0;
		}
		visit1[1] = 1;
		visit2[2] = 1;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				duongdi[i][j] = 0;
			}
		}
		for(int i = 0; i < m; i++){
			int x, y;
			cin >> x;
			cin >> y;
			duongdi[x][y] = 1;
		}
		kq1 = kq2 = 1000;
		go1(1,1);
		go2(2,1);
		cout << kq1 + kq2<< endl;
	}
	return 0;
}