Loading...
Loading...
Loading...
A project has n tasks and m rules "a b", meaning task a must be finished before task b starts. Every task takes exactly one round, and any number of tasks may run in the same round if their rules allow it. Print the smallest number of rounds, or -1 if the rules cannot be satisfied.
Example 1
Input
5 4 1 3 2 3 3 4 3 5
Output
3
Round 1: tasks 1 and 2. Round 2: task 3. Round 3: tasks 4 and 5.
Example 2
Input
2 2 1 2 2 1
Output
-1
Try the problem first. Open one hint at a time.
Run Kahn's algorithm and keep a level for every task.
When a task is released, its level is the largest level of its prerequisites plus one.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor