← 返回 scale.ai 的题目列表Task Processor with Subtasks: a task becomes runnable only after all its subtasks finish
类型：online_judge
Problem: Task Processor with Subtasks (a task becomes runnable only after all its subtasks finish)
Building on the basic Task Processor, each task may have multiple subtasks. A task can be processed only after all of its subtasks have been processed.
Given:
n tasks labeled 1..n
m subtask-to-task associations (a subtask belongs to a parent task)
Output a processing order that satisfies:
All subtasks must be processed before their parent task becomes runnable.
Among all currently runnable tasks, always process the one with the smallest deadline (tie-break by smaller task id).
For simplicity, subtasks have unique ids and have no dependencies among themselves; the only constraint is that they must be completed before the parent task.
Input (stdin)
First line: two integers n m
Second line: n integers d1 d2 ... dn where di is the deadline of task i
Next m lines: subtask_id parent_task_id meaning subtask_id belongs to parent_task_id
Processing rules:
Process all subtasks first (you may process subtasks in increasing subtask_id).
When all subtasks of a task are processed, the task is unlocked and pushed into a priority queue.
Repeatedly pop the runnable task with the smallest deadline (tie-break by smaller id).
Output (stdout)
Print two lines:
The subtask processing order (space-separated).
The task processing order (space-separated).
Constraints
1 <= n <= 2 * 10^5
0 <= m <= 2 * 10^5
subtask_id are positive and unique
Example
Input:
3 4
10 5 7
1 1
2 1
3 2
4 3
Output:
1 2 3 4
2 3 1
Example
Input
3 4
10 5 7
1 1
2 1
3 2
4 3
Output
1 2 3 4
2 3 1