from collections import deque, defaultdict

class Solution:
  # BFS
  # def sort(self, vertices, edges):
  #   in_degree = [0] * vertices
  #   adj_list = defaultdict(list)
  #   for from_node, to_node in edges:
  #     adj_list[from_node].append(to_node)
  #     in_degree[to_node] += 1
    
  #   queue = deque()
  #   for node_index in range(len(in_degree)):
  #     if in_degree[node_index] == 0: # source node, can be processed and remove
  #       queue.append(node_index)
  #   result = []
  #   while queue:
  #     current_node = queue.popleft()
  #     result.append(current_node)
  #     for neighbor in adj_list[current_node]:
  #       in_degree[neighbor] -= 1
  #       if in_degree[neighbor] == 0:
  #         queue.append(neighbor)
  #   if len(result) != vertices:
  #     return []
  #   return result
  
  #DFS
  def sort(self, vertices, edges):
    graph = defaultdict(list)
    for from_node, to_node in edges:
      graph[from_node].append(to_node)
    result = []
    visited = [False] * vertices
    has_cycle = False
    visited_current_dfs = [False] * vertices
    for i in range(vertices):
      if not visited[i]:
        if self.topSortUtil(i, visited, result, graph, visited_current_dfs):
          has_cycle = True
          break
    if has_cycle:
      return []
    return result[::-1]
  
  def topSortUtil(self, node, visited, result, graph, visited_current_dfs):
    visited[node] = True
    visited_current_dfs[node] = True
    for neighbor in graph[node]:
      if not visited[neighbor]:
        if self.topSortUtil(neighbor, visited, result, graph, visited_current_dfs):
          return True
      elif visited_current_dfs[neighbor]:
        return True
    visited_current_dfs[node] = False
    result.append(node)
    return False