from collections import deque, defaultdict

class Solution:
  # def isSchedulingPossible(self, tasks, prerequisites):
  #   # basically find out if there's a cycle in this graph
  #   # [2, 5], [0, 5], [0, 4], [1, 4], [3, 2], [1, 3] 6
  #   in_degree = [0] * tasks # [0, 0, 1, 0, 0, 1]
  #   adj_list = defaultdict(list) # {2: [5], 0: [5, 4], 1: [4, 3], 3: [2]}
  #   for prev_task, task in prerequisites:
  #     adj_list[prev_task].append(task)
  #     in_degree[task] += 1
  #   top_sort_result = [] # 0 1 
  #   queue = deque()
  #   for task in range(len(in_degree)):
  #     if in_degree[task] == 0:
  #       queue.append(task)
  #   while queue: # [4, 3]
  #     task = queue.popleft() # 0 1
  #     top_sort_result.append(task) 
  #     for neighbor in adj_list[task]: # 4 3
  #       in_degree[neighbor] -=1
  #       if in_degree[neighbor] == 0:
  #         queue.append(neighbor)
  #   if len(top_sort_result) == tasks:
  #     return True
  #   return False

#DFS
  def isSchedulingPossible(self, tasks, prerequisites):
      # basically find out if there's a cycle in this graph
      # [2, 5], [0, 5], [0, 4], [1, 4], [3, 2], [1, 3] 6
      visited = [False] * tasks
      visited_current_dfs = [False] * tasks
      adj_list = defaultdict(list) # {2: [5], 0: [5, 4], 1: [4, 3], 3: [2]}
      for prev_task, task in prerequisites:
        adj_list[prev_task].append(task)
      top_sort_result = [] # 0 1 
      for node in range(tasks):
        if not visited[node] and self.dfs_has_cycle(node, visited, visited_current_dfs, adj_list, top_sort_result):
          return False
      return True

  def dfs_has_cycle(self, node, visited, visited_current_dfs, adj_list, top_sort_result):
    visited[node] = True
    visited_current_dfs[node] = True

    for neighbor in adj_list[node]:
      if not visited[neighbor]:
        if self.dfs_has_cycle(neighbor, visited, visited_current_dfs, adj_list, top_sort_result):
          return True
      elif visited_current_dfs[neighbor]:
        return True
    top_sort_result.append(node)
    visited_current_dfs[node] = False
    return False