Cycle Detection in an Undirected Graph

You are given an undirected graph \(G = (V, E)\) with \(n\) nodes and \(m\) edges. Your task is to determine if the graph contains at least one cycle.

A cycle in an undirected graph is a path of edges and vertices wherein a vertex is reachable from itself. In other words, there exists a sequence \(v_1, v_2, \ldots, v_k\) (with \(k \ge 3\)) such that there is an edge between \(v_i\) and \(v_{i+1}\) for all \(1 \leq i < k\) and an edge between \(v_k\) and \(v_1\). You can assume that the graph might be disconnected, and you must consider all its components.

If there is at least one cycle in any component, output YES; otherwise, output NO.

inputFormat

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

n m
u1 v1
... 
um vm

Here, \(n\) is the number of nodes, \(m\) is the number of edges, and each of the next \(m\) lines contains two integers \(u\) and \(v\) representing an undirected edge between nodes \(u\) and \(v\).

outputFormat

Output a single line to standard output (stdout):

• YES if the graph contains at least one cycle.
• NO otherwise.

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

YES