Untitled

import java.util.Scanner;

public class Solution {
	static int N,M,u,v,f,r,ans;
	static int[][] ke,vs;
	static int[] len,q,d;
	public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for (int t = 1; t <= tc; t++) {
        	N = sc.nextInt();
        	M = sc.nextInt();
        	ke = new int[N+1][N+1];
        	len = new int[N+1];
        	for(int i=0;i<M;i++){
        		int x = sc.nextInt();
        		int y = sc.nextInt();
        		ke[x][len[x]++] = y;
        	}
        	vs = new int[2][N+1];
        	ans = Integer.MAX_VALUE;
        	vs[0][1] = 1;
        	DFS(1,0);
        	System.out.println(ans);
        }
	}
	static void DFS(int u, int k){
		if(u==1&&vs[1][u]==1){
			ans = Math.min(ans, count());
			return;
		}
		if(count()>=ans) return;
		for(int i=0;i<len[u];i++){
			if(vs[k][ke[u][i]]==0){
				if(ke[u][i]==2){
					vs[k][ke[u][i]]=1;
					vs[k+1][ke[u][i]]=1;
					DFS(ke[u][i],k+1);
					vs[k][ke[u][i]]=0;
					vs[k+1][ke[u][i]]=0;
				}
				else {
					vs[k][ke[u][i]]=1;
					DFS(ke[u][i],k);
					vs[k][ke[u][i]]=0;
				}
			}
		}
	}
	static int count(){
		int tmp = 0;
		for(int i=1;i<=N;i++){
			if(vs[0][i]!=0||vs[1][i]!=0) tmp++;
		}
		return tmp;
	}
}