Cycle in a Directed Graph

The graph has n nodes and directed edges [a, b] meaning an arrow from a to b. Return True if it contains a directed cycle (you can follow arrows and return to the start). A self-loop [a, a] is a cycle.

For n = 3 and edges = [[0, 1], [1, 2], [2, 0]] the answer is True.

Examples

Example 1

Input:

has_cycle_directed(3, [[0, 1], [1, 2], [2, 0]])

Output:

True

Example 2

Input:

has_cycle_directed(3, [[0, 1], [0, 2], [1, 2]])

Output:

False

Constraints

• 0 <= n <= 100000
• 0 <= len(edges) <= 200000