Overview

This problem requires determining the order in which to execute tasks while preserving the precedence relationships (dependencies) between them. Among the multiple orderings that satisfy the conditions, we need to find the lexicographically smallest one. If there is a contradiction (cycle) in the dependencies, we must detect it and output -1.

Analysis

If we treat tasks as “vertices” and prerequisites (task \(B\) must be done after task \(A\)) as “directed edges \(A \to B\)”, this problem can be reduced to finding a topological sort in graph theory.

How do we achieve lexicographically smallest order?

In a standard topological sort, we can choose any available task (one whose all prerequisite tasks have been completed) as the next task to execute. However, this problem specifies “lexicographically smallest.” To minimize the lexicographic order, we must always prioritize selecting “the task with the smallest number among the currently executable tasks.”

When is there a contradiction?

If the dependencies form a loop (cycle), such as “task \(1 \to 2\)”, “task \(2 \to 3\)”, “task \(3 \to 1\)”, those tasks can never be executed. If, after performing the topological sort, the length of the resulting list is less than the total number of tasks \(N\), we can determine that the graph contains a cycle, meaning there is a contradiction.

Algorithm

We use Kahn’s algorithm as the base, employing a priority queue (min-heap) as the data structure.

1. Compute in-degrees: For each vertex, count the number of edges directed toward it (in-degree).
2. Initialization: Insert all vertices with in-degree \(0\) (tasks with no prerequisites) into the priority queue.
3. Iterative processing: Repeat the following until the queue is empty:
   • Extract the vertex \(u\) with the smallest number from the queue and append it to the result list.
   • Remove all edges going out from vertex \(u\). Specifically, decrease the in-degree of each adjacent vertex \(v\) of \(u\) by \(1\).
   • If any vertex \(v\) now has an in-degree of \(0\), add it to the queue.
4. Judgment: If the length of the result list is \(N\), output it; otherwise, output -1.

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • Each vertex and each edge is traversed once (\(O(N + M)\)).
  • Since insertion into and extraction from the priority queue each cost \(O(\log N)\), the overall complexity is \(O((N + M) \log N)\).
• Space complexity: \(O(N + M)\)
  • The adjacency list and the array for managing in-degrees use \(O(N + M)\) memory.

Implementation Tips

• Fast I/O: Since \(N, M\) can be as large as \(2 \times 10^5\), in Python, using sys.stdin.read().split() and sys.stdout.write can reduce execution time.

• Priority queue: Python’s heapq module provides a min-heap, so simply using it allows us to always retrieve the smallest element in \(O(\log N)\), easily satisfying the lexicographically smallest condition.

  Source Code

import sys
import heapq

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリスト化します。
    # 大量の入力を処理する場合、sys.stdin.read().split() は Python において効率的です。
    try:
        data = sys.stdin.read().split()
    except EOFError:
        return
        
    if not data:
        return
    
    # イテレータを使用してデータを順番に取得します。
    it = iter(data)
    try:
        N = int(next(it))
        M = int(next(it))
    except StopIteration:
        return
    
    # 隣接リストと各ノードの入次数を管理する配列を用意します。
    # タスク番号は 1 から N であるため、サイズを N + 1 にします。
    adj = [[] for _ in range(N + 1)]
    in_degree = [0] * (N + 1)
    
    # 前提条件 (Ai, Bi) を読み込み、グラフを構築します。
    for _ in range(M):
        try:
            u = int(next(it))
            v = int(next(it))
            adj[u].append(v)
            in_degree[v] += 1
        except StopIteration:
            break
    
    # 入次数が 0 のノード（前提条件がないタスク）を管理する最小ヒープを用意します。
    # 辞書順最小の順序を求めるため、常に最小の番号のタスクを選択するようにします。
    pq = []
    for i in range(1, N + 1):
        if in_degree[i] == 0:
            heapq.heappush(pq, i)
    
    result = []
    # Kahnのアルゴリズムを用いたトポロジカルソート
    while pq:
        # 入次数 0 のタスクのうち、番号が最小のものを取得します。
        u = heapq.heappop(pq)
        result.append(u)
        
        # 現在のタスクを完了したことで、依存していた後続タスクの入次数を減らします。
        for v in adj[u]:
            in_degree[v] -= 1
            # 入次数が 0 になったタスクは実行可能リスト（ヒープ）に追加します。
            if in_degree[v] == 0:
                heapq.heappush(pq, v)
    
    # すべてのタスクが実行できたか確認します（閉路がある場合は N 個未満になります）。
    if len(result) == N:
        # スペース区切りで出力します。
        sys.stdout.write(" ".join(map(str, result)) + "\n")
    else:
        # すべてのタスクを実行不可能な場合（矛盾がある場合）は -1 を出力します。
        sys.stdout.write("-1\n")

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.