Cycle Detection in Undirected Graph

You are given an undirected and unweighted graph. The graph is defined with $V$ vertices and $E$ edges. Your task is to determine whether or not the graph contains a cycle.

A cycle in an undirected graph is a path that starts and ends at the same vertex, with at least one edge repeated in reverse (i.e. not simply the edge leading back to the parent in a DFS tree). Remember that a connected component may not contain a cycle, while disconnected parts of the graph should be checked separately.

Constraints:

• $1 \leq T \leq 100$, where $T$ is the number of test cases.
• $2 \leq V \leq 1000$, where $V$ is the number of vertices.
• $1 \leq E \leq 2000$, where $E$ is the number of edges.
• $1 \leq u, v \leq V$, for each edge $(u,v)$.

Note: If there is any cycle in any component of the graph, print YES. Otherwise, print NO.

inputFormat

The input is given via standard input (stdin) with the following format:

• The first line contains an integer $T$, the number of test cases.
• For each test case:
  • The first line contains two space-separated integers $V$ and $E$, the number of vertices and edges respectively.
  • The next $E$ lines each contain two space-separated integers $u$ and $v$ indicating an edge between vertex $u$ and vertex $v$.

outputFormat

For each test case, output a single line containing either YES if the graph contains a cycle or NO if it does not. The output is printed to standard output (stdout).## sample

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

YES
NO