Cycle Detection in Directed Graph

You are given a directed graph with n nodes and m edges. Your task is to determine whether the graph contains any cycle.

The first line of input contains two integers \(n\) and \(m\) (\(1 \leq n \leq 10^5\), \(0 \leq m \leq 10^5\)). Each of the next \(m\) lines contains two integers \(u\) and \(v\) (\(1 \leq u, v \leq n\)), which represents a directed edge from node \(u\) to node \(v\). If the graph contains a cycle, print "1"; otherwise, print "0".

A cycle is defined as a non-empty sequence of nodes \(v_1, v_2, \dots, v_k\) (with \(k \geq 2\)) such that there is an edge from \(v_i\) to \(v_{i+1}\) for \(1 \leq i < k\), and an edge from \(v_k\) back to \(v_1\).

inputFormat

The input is read from standard input (stdin) and has the following format:

 n m
 u1 v1
 u2 v2
 ...
 um vm

Here, the first line contains two space-separated integers \(n\) and \(m\). Each of the next \(m\) lines contains two space-separated integers representing a directed edge from \(u\) to \(v\).

outputFormat

Output a single integer to standard output (stdout):
• Print "1" if there is a cycle in the directed graph.
• Otherwise, print "0".

4 3
1 2
2 3
3 4

0