Overview

Since the “must be done before” relationships between tasks can be represented as a directed graph, this problem asks us to find the lexicographically smallest topological sort.
By always choosing the smallest-numbered vertex among those with in-degree \(0\) (tasks that can be executed immediately), we obtain the lexicographically smallest order.

Analysis

The prerequisite “execute \(A_i\) before \(B_i\)” can be viewed as a directed edge \(A_i \to B_i\).
Then, an execution order satisfying all conditions is a “topological order of the directed graph.”

Key Insight

• At any point, the executable tasks are those among the unexecuted tasks with in-degree \(0\).
• To achieve the lexicographically smallest order, we simply choose the smallest-numbered task among the candidates each time (greedy).

Why a Naive Approach Is Difficult

• If we linearly search for the “smallest-numbered executable task” each time, it can be \(O(N^2)\) in the worst case.
• Since \(N, M \le 2 \times 10^5\), \(O(N^2)\) is too slow.

Solution

• Manage the set of vertices with in-degree \(0\) using a min-heap.
• This allows extracting the smallest-numbered vertex in \(O(\log N)\).
• Follow edges to decrement in-degrees, and add vertices to the heap when their in-degree becomes \(0\).

Additionally, if the total number of extracted tasks is less than \(N\) at the end, there is a cycle somewhere making execution impossible, so we output -1.

Algorithm

1. Build an adjacency list graph and an in-degree array indeg for each vertex.
   For each condition \((a, b)\):
   • graph[a].append(b)
   • indeg[b] += 1
2. Insert all vertices with in-degree \(0\) into a min-heap pq.
3. Repeat until pq is empty:
   • Extract the smallest vertex v and append it to the answer order
   • For each edge v -> nv, decrement indeg[nv] -= 1
   • If indeg[nv] == 0, add nv to pq
4. If the length of order is \(N\), output it as is; otherwise, output -1.

This procedure combines “Kahn’s algorithm (topological sort)” with a min-heap for lexicographic minimization.

Complexity

• Time complexity: \(O((N+M)\log N)\)
  (Heap operations for each vertex and in-degree updates for each edge)
• Space complexity: \(O(N+M)\)
  (Adjacency list, in-degree array, heap, answer array)

Implementation Notes

• Since vertex numbers range from \(1\) to \(N\), set the array size to N+1.

• The key to lexicographic minimization is heapq (min-heap). A deque cannot guarantee the lexicographically smallest order.

• Cycle detection can be done concisely with len(order) != N.
  This means “there are unprocessed vertices remaining even though no vertices with in-degree \(0\) are left.”

  Source Code

import sys
import heapq

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    
    graph = [[] for _ in range(N + 1)]
    indeg = [0] * (N + 1)
    
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        indeg[b] += 1
    
    pq = []
    for v in range(1, N + 1):
        if indeg[v] == 0:
            heapq.heappush(pq, v)
    
    order = []
    while pq:
        v = heapq.heappop(pq)
        order.append(v)
        for nv in graph[v]:
            indeg[nv] -= 1
            if indeg[nv] == 0:
                heapq.heappush(pq, nv)
    
    if len(order) != N:
        print(-1)
    else:
        print(*order)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.