Overview

This problem requires finding the lexicographically smallest execution order of tasks while satisfying “must be done before” dependency relationships between tasks.
It can be solved by performing a topological sort on the graph, always choosing “the task with the smallest number among those currently executable.”

Analysis

Each condition “Task \(A_i\) must be done before Task \(B_i\)” can be thought of as a directed edge \(A_i \to B_i\).

The problem then becomes:

• Given a directed graph,
• arrange the vertices so that all edge directions are respected,
• and find the lexicographically smallest such arrangement.

This is exactly a topological sort problem.

Key Observation

At any given point, the tasks that can be executed are those among the unfinished tasks whose prerequisites have all been completed.

In graph terms, these correspond to vertices with in-degree \(0\).
This is because no incoming edges to that task means “there are no unfinished prerequisite tasks remaining.”

How to Achieve Lexicographically Smallest Order?

In a standard topological sort, picking any vertex with in-degree \(0\) yields a valid order.
However, since we want the lexicographically smallest order:

• If there are multiple executable tasks,
• always choose the one with the smallest number.

To perform this operation efficiently, we manage the vertices with in-degree \(0\) using a min-heap.

Why a Naive Approach Doesn’t Work

For example, if at each step we:

1. Scan all tasks to find those with in-degree \(0\)
2. Select the one with the smallest number

then each step takes \(O(N)\), resulting in \(O(N^2)\) overall.
Since \(N \leq 2 \times 10^5\), this is too slow.

Instead, by:

• Managing in-degrees with an array
• Adding tasks to the heap when their in-degree becomes \(0\)
• Extracting the smallest number from the heap

we can process everything efficiently.

When Execution is Impossible

If the prerequisites contain contradictions, the graph will have a cycle.

Example: - \(1 \to 2\) - \(2 \to 3\) - \(3 \to 1\)

In this case, every task requires some other task to be done first, so no task can be started.
In topological sort, the total number of vertices placed in the order will be less than \(N\).
When this happens, we output -1.

Algorithm

The solution follows these steps:

1. Build the graph as an adjacency list

   • Add edge \(A_i \to B_i\)
   • At the same time, increment the in-degree of \(B_i\) by \(1\)

2. Add all tasks with in-degree \(0\) to a min-heap

3. Repeat the following until the heap is empty:

   • Extract the smallest task number \(v\) from the heap
   • Append it to the answer
   • For each edge \(v \to nv\) going out from \(v\):
     • Decrease the in-degree of \(nv\) by \(1\)
     • If the in-degree becomes \(0\), add it to the heap

4. Finally, check the number of tasks in the answer:

   • If it is \(N\), output that order
   • If it is less than \(N\), there is a cycle, so output -1

Concrete Example

For example, given:

• \(1 \to 3\)
• \(2 \to 3\)

Initially, tasks \(1\) and \(2\) can be executed.
To achieve lexicographically smallest order, we first choose \(1\).
Next, \(2\) is still available, so we choose \(2\), and finally \(3\) becomes available.

Thus the answer is
\(1, 2, 3\).

If we chose arbitrarily without using a heap, we might get \(2, 1, 3\), but this is not lexicographically smallest.

Complexity

• Time complexity: \(O((N + M)\log N)\)
• Space complexity: \(O(N + M)\)

Implementation Notes

• Build the graph as an adjacency list using adj[a].append(b)
• Manage in-degrees with indeg[b] += 1
• To achieve lexicographically smallest order, use a min-heap instead of a queue for the set of vertices with in-degree \(0\)
• At the end, if len(order) != n, there is a cycle making execution impossible, so output -1

This code is a straightforward implementation of exactly this approach.

Source Code

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    n, m = data[0], data[1]
    adj = [[] for _ in range(n + 1)]
    indeg = [0] * (n + 1)

    idx = 2
    for _ in range(m):
        a = data[idx]
        b = data[idx + 1]
        idx += 2
        adj[a].append(b)
        indeg[b] += 1

    h = []
    for i in range(1, n + 1):
        if indeg[i] == 0:
            heapq.heappush(h, i)

    order = []
    while h:
        v = heapq.heappop(h)
        order.append(v)
        for nv in adj[v]:
            indeg[nv] -= 1
            if indeg[nv] == 0:
                heapq.heappush(h, nv)

    if len(order) != n:
        print(-1)
    else:
        print(*order)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.