Cycle Detection in Directed Graph

Given a directed graph with \(n\) nodes and \(m\) edges, determine whether the graph contains a cycle.

A cycle is defined as a sequence of vertices \(v_1, v_2, \dots, v_k\) such that \(v_1 = v_k\) and for every \(1 \le i < k\), there exists a directed edge \((v_i, v_{i+1})\). You are required to use a Depth-First Search (DFS) approach with a recursion stack to detect cycles in the graph.

Read the input from STDIN and output the result to STDOUT.

inputFormat

The input is read from STDIN. The first line contains a single integer (T) representing the number of test cases. For each test case, the first line contains two integers (n) and (m) where (n) is the number of nodes and (m) is the number of directed edges. This is followed by (m) lines, each containing two integers (u) and (v) which represent a directed edge from node (u) to node (v).

outputFormat

For each test case, output a single line containing "YES" if the graph contains a cycle, or "NO" otherwise.## sample

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

YES
NO