Cycle Detection in an Undirected Graph

You are given an undirected graph with N vertices and M edges. Your task is to determine whether the graph contains a cycle. A cycle in an undirected graph is a path starting and ending at the same vertex, with at least one edge repeated, and not simply the trivial path.

The input guarantees that the vertices are labeled from 1 to N. You are to analyze the graph using any method of your choice (for example, DFS) and output YES if there is a cycle, or NO otherwise.

Formally, if we denote the vertices by \(V = \{1,2,\dots,N\}\) and the edges by \(E\), determine if there exists a sequence of distinct vertices \(v_1, v_2, \dots, v_k\) (with \(k \ge 3\)) such that \((v_1, v_2), (v_2, v_3), \dots, (v_{k-1}, v_k)\) and \((v_k, v_1)\) are all in \(E\).

inputFormat

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

N M
u1 v1
u2 v2
... (M lines total)

Where:

• N is the number of vertices.
• M is the number of edges.
• Each subsequent line contains two integers u and v representing an undirected edge between vertices u and v.

outputFormat

Output a single line to the standard output (stdout) containing either YES if there is a cycle in the graph or NO if there is no cycle.

3 3
1 2
2 3
3 1

YES