Description

Given a directed graph with $n$ vertices, determine whether there exists a negative cycle that is reachable from vertex $1$.

A negative cycle is defined as a cycle whose sum of edge weights is negative.

Input Format

This problem contains multiple groups of testdata in a single test point.

The first line contains an integer $T$, representing the number of groups of testdata. For each group, the format is as follows:

The first line contains two integers, the number of vertices $n$ and the number of lines $m$ of edge information that follow.

Then follow $m$ lines, each with three integers $u, v, w$.

• If $w \geq 0$, then there exists an edge from $u$ to $v$ with weight $w$, and also an edge from $v$ to $u$ with weight $w$.
• If $w < 0$, then there exists only an edge from $u$ to $v$ with weight $w$.

Output Format

For each group of testdata, output one line containing a string. Print YES if such a negative cycle exists, otherwise print NO.

2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8

NO
YES

Hint

Constraints and Conventions

For all test points, it is guaranteed that:

• $1 \leq n \leq 2 \times 10^3$, $1 \leq m \leq 3 \times 10^3$.
• $1 \leq u, v \leq n$, $-10^4 \leq w \leq 10^4$.
• $1 \leq T \leq 10$.

Hint

Please note that $m$ is not the number of edges of the graph.

Translated by ChatGPT 5