Cycle Detection in Undirected Graphs

You are given an undirected graph described by its nodes and edges. Your task is to determine whether the graph contains a cycle. A cycle in a graph is defined as a sequence of edges and vertices wherein a vertex is reachable from itself by traversing the edges, with at least one edge, and without reusing the edge immediately in the reverse direction.

The graph may be disconnected, so you need to check each connected component independently. For each test case, if any cycle exists in any connected component of the graph, output YES; otherwise, output NO.

Note: Two vertices connected by an edge imply an undirected connection. If there is any cycle in any component, the answer is YES.

The cycle condition in undirected graphs is mathematically defined as follows:

$$\text{A cycle exists if there is a path } v_1 \to v_2 \to \cdots \to v_k \to v_1 \text{ with } k \ge 3.$$

inputFormat

The first line of input contains a single integer T denoting the number of test cases.

For each test case, the first line contains two integers N and M — the number of nodes and the number of edges respectively. This is followed by M lines, each containing two integers u and v which represent an undirected edge between nodes u and v.

Input Format Summary:

T
N M
u1 v1
u2 v2
... (M lines per test case)

outputFormat

For each test case, output a single line containing YES if a cycle exists in the graph, and NO otherwise.

## sample

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

YES
NO

</p>