Cycle Detection in Graphs

You are given an undirected graph and your task is to detect whether the graph contains a cycle. A cycle in an undirected graph means that there is a path (or sequence of edges) that starts and ends at the same vertex with no repetition of edges.

The graph is given in a specific format where the first line contains an integer T, the number of test cases. Each test case begins with two integers n and m representing the number of nodes and edges respectively, followed by m lines each containing two integers u and v denoting an edge between node u and node v.

Your program should output "Yes" if there is a cycle in the graph, otherwise output "No". If there are multiple test cases, output the result for each test case in a separate line.

The underlying algorithm can be implemented using Depth First Search (DFS) or the Union-Find (Disjoint Set Union) method. In DFS, during the traversal one should check for back-edges indicating a cycle. In Union-Find, while processing each edge if the two vertices belong to the same set, a cycle is detected.

For a mathematical formulation, let \(G=(V,E)\) be an undirected graph, and let \(\text{DFS}(v)\) be a depth-first search starting from vertex \(v\). A cycle exists if there is an edge \((u,v)\) such that \(v\) is already visited and \(v\) is not the parent of \(u\). That is, a cycle is detected if:

\[ \exists\, (u,v) \in E, \text{ such that } v \text{ is visited and } v \neq \text{parent}(u). \]

inputFormat

The input is read from stdin and structured as follows:

1. The first line contains an integer T, the number of test cases.
2. For each test case, the first line contains two integers n and m, representing the number of nodes and edges respectively.
3. This is followed by exactly m lines, each containing two space-separated integers u and v representing an undirected edge between nodes u and v.

It is assumed that the nodes are numbered from 1 to n.

outputFormat

For each test case, output a single line to stdout with the answer: either "Yes" if the graph contains a cycle or "No" if it does not.

## sample

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

Yes
No

</p>