Untitled

package OnLan2;

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

public class diAnCuoi {
	static int N, ans, M, a[][], visit[], visit2[];

	public static void main(String[] args) {

		try {
			System.setIn(new FileInputStream("anCuoi"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();

		for (int t = 1; t <= T; t++) {
			N = scanner.nextInt();
			M = scanner.nextInt();
			a = new int[N + 2][N + 2];
			for (int i = 1; i <= M; i++) {
				int x = scanner.nextInt();
				int y = scanner.nextInt();
				a[x][y] = 1;
			}
			visit = new int[N + 2];
			visit2 = new int[N + 2];
			ans = Integer.MAX_VALUE;
			visit[1] = 1;
			DFS(1);
			System.out.println("#" + t);
			System.out.println(ans);
		}
	}

	public static void DFS(int start) {
		if (NumDinh() > ans) {
			return;
		}
		if (start == 2) {
			visit2[2] = 1;
			DFS2(start);
			return;
		}
		for (int i = 1; i <= N; i++) {
			if (visit[i] == 0 && a[start][i] == 1) {
				visit[i] = 1;
				DFS(i);
				visit[i] = 0;
			}
		}
	}

	public static void DFS2(int start) {
		if (NumDinh() > ans) {
			return;
		}
		if (start == 1) {
			ans = Math.min(ans, NumDinh());
			return;
		}
		for (int i = 1; i <= N; i++) {
			if (visit2[i] == 0 && a[start][i] == 1) {
				visit2[i] = 1;
				DFS2(i);
				visit2[i] = 0;
			}
		}
	}

	public static int NumDinh() {
		int dinh = 0;
		for (int i = 1; i <= N; i++) {
			if ((visit[i] + visit2[i]) != 0) {
				dinh++;
			}
		}
		return dinh;

	}
}