Cycle Detection in Directed Graph

You are given a directed graph with \( n \) vertices and \( m \) edges. Your task is to determine whether the graph contains a cycle. A cycle exists if there is a sequence of distinct vertices \( v_1, v_2, \ldots, v_k \) such that there is a directed edge from \( v_i \) to \( v_{i+1} \) for \( 1 \leq i < k \) and an edge from \( v_k \) back to \( v_1 \). Note that a self-loop (an edge from a vertex to itself) is also considered a cycle.

The input consists of multiple test cases. For each test case, determine if the corresponding directed graph contains any cycle. Output YES if a cycle exists and NO otherwise.

inputFormat

The input is read from stdin and has the following format:

T
n1 m1
u1 v1
u2 v2
... (m1 lines)
n2 m2
... (edges for test case 2)
...

Where:

• T is the number of test cases.
• For each test case, the first line contains two integers \( n \) and \( m \), representing the number of vertices and the number of edges respectively.
• Then follow \( m \) lines each containing two integers \( u \) and \( v \), indicating a directed edge from vertex \( u \) to vertex \( v \).

outputFormat

For each test case, output a single line to stdout:

• YES if the graph contains a cycle, or
• NO if the graph has no cycle.

## sample

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

YES
NO

</p>