Cycle Detection in Directed Graph

You are given a directed graph with \( n \) vertices and \( m \) edges. Your task is to determine whether the graph contains a cycle. A cycle exists if there is a sequence of vertices \( v_1, v_2, \ldots, v_k \) (with \( k \ge 1 \)) such that there is a directed edge from \( v_i \) to \( v_{i+1} \) for \( 1 \leq i < k \) and an edge from \( v_k \) back to \( v_1 \).

Hint: You can use Depth-First Search (DFS) to detect cycles in the graph by keeping track of the recursion stack. In DFS, mark nodes as:

• \( 0 \): unvisited,
• \( 1 \): visiting (in the recursion stack),
• \( 2 \): visited.

If you visit a node that is already in the recursion stack (i.e. marked with \( 1 \)), then a cycle is detected.

inputFormat

The first line of input contains an integer \( n \) denoting the number of vertices. The second line contains an integer \( m \) denoting the number of directed edges. The next \( m \) lines each contain two integers \( u \) and \( v \), representing an edge from vertex \( u \) to vertex \( v \).

Note: The vertices are numbered from 1 to \( n \).

outputFormat

Print "YES" if the graph contains a cycle; otherwise, print "NO".

4
3
1 2
2 3
3 4

NO