Cycle Detection in an Undirected Graph

You are given an undirected graph with (n) vertices and (m) edges. Your task is to determine if the graph contains any cycle. A cycle is present if there exists a sequence of vertices (v_1, v_2, \ldots, v_k) (with (k \geq 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).

Input: The input consists of multiple test cases. The first line contains a single integer (T), the number of test cases. For each test case, the first line contains two integers (n) and (m) representing the number of vertices and edges, respectively. The following (m) lines each contain two integers (u) and (v) denoting an undirected edge between vertices (u) and (v).

Output: For each test case, output a single line containing True if the graph contains at least one cycle, otherwise output False.

inputFormat

Standard Input Format:

• The first line contains an integer (T), the number of test cases.
  
• For each test case:
      - The first line contains two integers (n) and (m).
      - Each of the next (m) lines contains two integers (u) and (v), representing an edge between vertices (u) and (v).

outputFormat

Standard Output Format:

For each test case, output on a new line True if the graph contains a cycle, otherwise output False.## sample

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

True
False
True
False
True