Untitled

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

public class FindCycle_DFS2 {
	private static int V; // Số đỉnh
	private static int E; // Số cạnh
	private static int[][] adj; // Ma trận kề
	private static boolean[] visited; // Mảng đánh dấu các đỉnh đã duyệt

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\APS2\\FindCycle_input.txt"));
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			V = scanner.nextInt();
			E = scanner.nextInt();
			adj = new int[V][V];
			for (int i = 0; i < E; i++) {
				int u = scanner.nextInt() - 1;
				int v = scanner.nextInt() - 1;
				adj[u][v] = 1;
			}
			visited = new boolean[V];
			boolean hasCycle = false;
			for (int i = 0; i < V; i++) {
				if (isCyclic(i)) {
					hasCycle = true;
					break;
				}
			}
			System.out.println("Case #" + tc);
			System.out.println(hasCycle ? 1 : 0);
		}
		scanner.close();
	}

	private static boolean isCyclic(int v) {
		boolean[] recStack = new boolean[V];
		Stack<Integer> stack = new Stack<>();
		stack.push(v);
		while (!stack.isEmpty()) {
			v = stack.pop();
			if (recStack[v]) {
				return true;
			}
			if (!visited[v]) {
				visited[v] = true;
				recStack[v] = true;
				for (int u = 0; u < V; u++) {
					if (adj[v][u] == 1) {
						stack.push(u);
					}
				}
			}
			recStack[v] = false;
		}
		return false;
	}
}