diancuoi

#include <iostream>

using namespace std;

int n, m;

int a[50][50];
int start, endd;

int queue[10000000];
int front, rear;
int visit[50];
int res;
int check[50];
void resetvisit() {
	for (int i = 1; i <= n; i++) {
		visit[i] = 0;
	}
}

void dfs(int x, int count) {
	if (x == endd) {
		if (count - 1 < res) {
			res = count - 1;
		}
	}
	visit[x] = 1;
	for (int i = 1; i <= n; i++) {
		if (visit[i] == 0 && a[x][i] == 1) {
			if (check[i] == 0) {
				dfs(i, count + 1);
				check[i] = 1;
			} 
			else {
				dfs(i, count);
			}
			
		}
		
		if (a[x][i] == 1 && visit[i] == 1 && i == endd) {
			if (count < res) {
				res = count;
			}	
		}
		
	}
}

void solve(int testcase) {
	cin >> n >> m;

	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		a[x][y] = 1;
	}
	/*
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
	*/
	for (int i = 1; i <= n; i++) {
		check[i] = 0;
	}
	int ans = 0;
	resetvisit();
	start = 1;
	endd = 2;
	res = 100;
	dfs(start, 0);
	cout << res << endl;
	resetvisit();
	start = 2;
	endd = 1;
	res = 100;
	dfs(start, 0);
	cout << res << endl;
}

int main() {
	freopen("Text.txt", "r", stdin);
	int t; cin >> t;

	for (int i = 1; i <= t; i++) {
		solve(i);
	}
	return 0;
}


4
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
12 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 1
16 144
3 9
10 3
1 14
6 10
12 2
10 9
11 6
12 11
16 11
3 1
14 12
5 10
15 7
1 15
9 16
6 12
8 16
14 8
13 4
2 8
5 11
16 15
10 16
16 3
8 5
12 6
11 12
4 3
11 10
14 3
9 12
10 5
15 11
13 3
2 5
7 11
4 12
6 4
14 13
8 9
3 2
4 6
4 14
15 2
16 7
13 10
4 8
13 9
3 14
14 9
8 1
4 1
10 11
2 16
1 9
7 13
7 6
9 3
14 11
1 11
12 7
5 15
8 15
4 5
11 4
13 1
2 6
4 10
9 1
4 9
14 5
3 15
14 2
15 1
11 7
15 12
5 14
2 7
16 6
8 6
12 10
6 5
9 6
13 6
6 1
1 7
14 15
10 8
2 13
3 8
6 14
2 10
16 14
15 6
9 5
6 9
11 3
8 12
5 4
1 8
6 7
1 5
15 16
2 14
3 12
7 1
13 5
3 16
7 8
7 10
14 7
7 16
9 11
9 10
5 1
1 16
10 4
6 16
10 7
7 3
11 1
2 12
12 13
13 15
15 10
4 15
5 8
16 4
8 13
7 12
6 8
7 2
4 13
10 14
15 13
15 3
11 15
6 15
16 10
1 6
7 5
8 4
10 6
1 13

#include <iostream>

using namespace std;

int n, m;

int map[100][100];
int check[100];
int vs[100];
int minans;
int kt;

void DFS(int st, int ed)
{
	vs[st] = 1;
	if (st == ed) kt = true;
	if (kt == true) return;
	for (int i = 1; i <= n; i++)
		if (check[i] == 1 && map[st][i] == 1 &&  vs[i] == 0)
			DFS(i,ed);
}

int checkk()
{
	kt = false;
	for (int i = 1; i<=n; i++)
		vs[i] = 0;
	DFS(1,2);
	if (kt == false)
		return 0;
	else
	{
		for (int i = 1; i<=n; i++)
			vs[i] = 0;
		kt = false;
		DFS(2,1);
	}

	if (kt == false)
		return 0;
	return 1;
}

void backtrack(int index, int cost)
{
	if (index == n + 1)
	{
		if (cost < minans && checkk() == 1)
		{
			minans = cost;
		}
		return;
	}
	if (cost >= minans) return;
	for (int i = 0; i <=1; i++)
		if (i == 0)
			backtrack(index + 1, cost);
		else 
			{
				check[index] = 1;
				backtrack(index + 1, cost + 1);
				check[index] = 0;
		    }
}

int main()
{
//	freopen("input.txt","r",stdin);
	int ntc;
	cin >> ntc;
	for (int tc=1; tc<=ntc; tc++)
	{
		cin >> n >> m;
		for (int i = 0; i<= n+1; i++)
			for (int j = 0; j<= n+1; j++)
				map[i][j] = 0;
		for (int i = 1; i <= m; i++)
		{
			int xx, yy;
			cin >> xx >> yy;
			map[xx][yy] = 1;
		}
		minans = 99999;
		check[1] = 1;
		check[2] = 1;
		backtrack(3, 0);
		cout << minans + 2 << endl;
	}

	return 0;
}