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);
		}
	}
}