Untitled

import java.util.Scanner;

public class Solution {

	static int N, M, min;
	static int[][] a;
	static boolean[] visited, total, visited2;

	static void solve(int u) {
		int count = 0;
		for (int i = 1; i <= N; i++) {
			if (visited[i]) {
				count++;
			}
		}
		if (count >= min) {
			return;
		}
		if (u == 2) {
			for (int i = 1; i <= N; i++) {
				total[i] = visited[i];
				visited2[i] = false;
			}
			visited[2] = true;
			solve2(u);
			return;
		}
		for (int v = 1; v <= N; v++) {
			if (a[u][v] == 1 && !visited[v]) {
				visited[v] = true;
				solve(v);
				visited[v] = false;
			}
		}
	}

	static void solve2(int u) {
		int count = 0;
		for (int i = 1; i <= N; i++) {
			if (total[i] || visited2[i]) {
				count++;
			}
		}
		if (count >= min) {
			return;
		}
		if (u == 1) {
			count = 0;
			for (int i = 1; i <= N; i++) {
				if (total[i] || visited2[i]) {
					count++;
				}
			}
			min = count < min ? count : min;
		}
		for (int v = 1; v <= N; v++) {
			if (a[u][v] == 1 && !visited2[v]) {
				visited2[v] = true;
				solve2(v);
				visited2[v] = false;
			}
		}
	}

    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tcs = sc.nextInt();
		for (int tc = 1; tc <= tcs; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			a = new int[N + 1][N + 1];
			visited = new boolean[N + 1];
			visited2 = new boolean[N + 1];
			total = new boolean[N + 1];
			visited[1] = true;
			visited2[2] = true;
			for (int i = 0; i < M; i++) {
				a[sc.nextInt()][sc.nextInt()] = 1;
			}
			min = 10000000;
			solve(1);
			System.out.println(min);
		}
	}
}



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