Problem statement
Given a simple undirected graph with N vertices numbered from 1 to N and M edges, determine whether it contains a cycle. Simple means that there are no self-loops and no duplicate undirected edges. A cycle has at least three distinct vertices, with consecutive vertices and the first and last vertices connected by edges. The graph may be disconnected.
Input format
The first line contains N and M. Each of the next M lines contains the two distinct endpoints U and V of an edge. Every undirected edge appears at most once.
Output format
Print YES if any component contains a cycle. Otherwise, print NO.
Constraints
- 1 ≤ N ≤ 100000
- 0 ≤ M ≤ min(200000, N(N−1)/2)
- 1 ≤ U, V ≤ N; U ≠ V
- No duplicate undirected edges
Sample input
4 4 1 2 2 3 3 1 3 4
Sample output
YES
Sample explanation
Vertices 1, 2, and 3 form the cycle 1–2–3–1. The edge to vertex 4 is not part of the cycle.
Need a hint?
In an undirected DFS, the edge to the parent is not evidence of a cycle. Explore every connected component. Use an iterative traversal if a deep recursive call stack is unsafe.