Cycle Detection in an Undirected Graph

Given an undirected graph with n vertices (numbered from 0 to n-1) and m edges, your task is to determine whether the graph contains any cycle. A cycle is a path of edges and vertices wherein a vertex is reachable from itself by a sequence of edges, with no edge being repeated. The graph may be disconnected.

Input Format: The first line contains two integers n and m. Each of the next m lines contains two integers u and v representing an undirected edge between vertices u and v.

Output Format: Output 1 if the graph contains a cycle, otherwise output 0.

inputFormat

The first line of input contains two space-separated integers n (number of vertices) and m (number of edges). This is followed by m lines each containing two space-separated integers u and v, which denote an undirected edge between vertex u and vertex v.

outputFormat

Print a single integer: 1 if the graph has a cycle, and 0 if it does not.## sample

4 4
0 1
1 2
2 3
3 0

1