Untitled

//di an cuoi
package bal;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int soDinh;
	static int soCanh;
	static int ans;
	static int map[][];
	static int vis[];
	public static void resetVis(){
		for (int i = 0; i < soDinh; i++) {
			vis[i] = 0;
		}
	}
	public static void backTrack (int x , int sum){
		if(x == 0 && vis[0] == 2){
			if(vis[1] != 0){
				ans = Math.min(sum, ans);
			}
			return;
		}
		
		if(sum > ans){
			return;
		}
		
		for (int i = 0; i < soDinh; i++) {
			if(map[x][i] == 1 && vis[i] < 2){
				if(vis[i] == 0){
					vis[i]++;
					backTrack(i, sum+1);
					vis[i]--;
				}else if(vis[i] == 1){
					vis[i]++;
					backTrack(i, sum);
					vis[i]--;
				}
			}
		}
	}
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			soDinh = sc.nextInt();
			soCanh = sc.nextInt();
			
			map = new int [soDinh][soDinh];
			vis = new int [soDinh+1];
			
			for (int i = 0; i < soCanh; i++) {
				int start = sc.nextInt();
				int end = sc.nextInt();
				map[start-1][end-1] = 1;
			}
			
			ans = 100000;
			vis[0] = 1;
			backTrack(0,1);
			System.out.println(ans);
		}
	}
}

//

2

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
///

6
6

9 1