Untitled

package BackTracking;

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

public class Di_An_Cuoi {
	static int T, N, edges;
	static int map[][], index[], arrGo[], arrBack[];
	static int sumNode;
	
	public static void backTrackGo(int node, int countNode) {
		if(node == 2) {
			if(countNode < sumNode) 
				sumNode = countNode++;
			backTrackBack(2, sumNode);
		}
		
		for(int i = 0; i <= index[node]; i++) {
			if(arrGo[i] == 1) continue;
			arrGo[i] = 1;
			backTrackGo(map[node][index[i]], countNode+1);
			arrGo[i] = 0;
		}
	}
	
	public static void backTrackBack(int node, int countNode) {
		if(node == 1) {
			if(countNode < sumNode) 
				sumNode = countNode++;
		}
		
		for(int i = 0; i <= index[node]; i++) {
			if(arrBack[i] == 1) continue;
			else {
				if(arrGo[ map[node][i]] == 1)
					backTrackBack(map[node][i], countNode);
				else
					arrBack[map[node][i]] = 1;
					backTrackBack(map[node][i], countNode+1);
					arrBack[map[node][i]] = 0;
			}
			
		}
	}
	
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src/BackTracking/Di_An_Cuoi"));
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt();
		for(int tc = 1; tc <= T; tc++) {
			N = scanner.nextInt();
			edges = scanner.nextInt();
			map = new int[N+1][N+1];
			index = new int[N+1];
			arrGo = new int[N+1];
			arrBack = new int[N+1];
			
			int value;
			for(int i = 0; i < edges; i++) {
				value = scanner.nextInt();
				map[value][index[value]++] = scanner.nextInt();
			}
			
			arrGo[1] = 1;
			arrBack[2] = 1;
			sumNode = 0;
			backTrackGo(0, 0);
			System.out.println(sumNode);
		}
	}
}