Deadlock Detection

Difficulty: 1600 4000 ms 128 MB

graphs

Tasks point at the tasks they wait for (directed edges). Is there a deadlock — a directed cycle?

Input: the first line has N and M; each of the next M lines has a directed edge u → v (1-based).

Output: YES if a directed cycle exists, else NO.

Constraints:

• 1 ≤ N ≤ 10⁴
• 0 ≤ M ≤ 2×10⁴
• multiple edges and self-loops may appear

Sample Tests

3 3
1 2
2 3
3 1

YES

3 2
1 2
1 3

NO

Read the Editorial