import java.util.*;
public class Solution {
  /** In a Directed Acyclic Graph (DAG), topological sorting can process all nodes. If some nodes cannot be processed due to non-zero indegree, a cycle exists. */
  public static boolean detectCycleInDirectedGraph(int n, ArrayList < ArrayList < Integer >> edges) {

    // Step 1: Create adjacency list
    ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
    for(int i=0; i<=n; i++)
    {
      adj.add(new ArrayList<>());
    }

    // Step 2: Fill adjacency list and indegree array
    int[] indegree = new int[n+1];
    for(ArrayList<Integer> edge : edges) {
      int u = edge.get(0);
      int v = edge.get(1);

      adj.get(u).add(v);
      indegree[v]++;
    }

    //Step-3 check which all nodes has an indegree as 0, add those nodes to queue
    Queue<Integer> q = new LinkedList<>();
    for(int i=1; i<=n; i++)
    {
      if(indegree[i] == 0)
        q.add(i);
    }

    // Step-4: Process queue
    int count = 0;
    while(!q.isEmpty())
    {
      int node = q.poll();
      count++;

      // traverse all neighbour of current node
      for(int u : adj.get(node))
      {
        indegree[u]--;
        if(indegree[u] == 0)
          q.add(u);
      }
    }

    // Step-5: Check cycle
    return count != n;
  }
}