Loading...
Loading...
Loading...
A project has n tasks numbered 1 to n and m rules. A rule "a b" means task a must be finished before task b starts. Print YES if all tasks can be done in some order that obeys every rule, and NO if the rules contradict each other.
Example 1
Input
4 4 1 2 1 3 2 4 3 4
Output
YES
Order 1, 2, 3, 4 works.
Example 2
Input
3 3 1 2 2 3 3 1
Output
NO
The rules form a ring.
Try the problem first. Open one hint at a time.
Count how many rules point into each task.
Repeatedly remove a task with no unfinished rule pointing into it. If some tasks can never be removed, there is a ring.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor