Cycle Detection in an Undirected Graph

You are given an undirected graph represented with V vertices and E edges. Your task is to determine whether the graph contains a cycle.

A cycle is defined as a path (or a sequence of edges) starting and ending at the same vertex, with at least one edge repeated in the traversal, such that not every repeated vertex is the immediate parent in the DFS traversal. Mathematically, for a graph G=(V,E), a cycle exists if there exist vertices v0, v1, ..., vk (with k \ge 2) such that:

\(v_0 = v_k\) and for each \(0 \le i < k\), \((v_i, v_{i+1}) \in E\) and the cycle is not trivial.

You need to implement an algorithm (using DFS or any other appropriate method) that reads the graph from standard input and prints True if there is a cycle, and False otherwise.

inputFormat

The input is given in the following format from standard input:

V E
u1 v1
u2 v2
... 
ue v e

where:

• V is the number of vertices.
• E is the number of edges.
• Each of the next E lines contains two integers u and v representing an undirected edge between vertices u and v.

outputFormat

Print to standard output a single line with either True or False indicating whether the graph contains a cycle.

## sample

5 5
0 1
1 2
2 3
3 4
4 1

True