【模板】负环

题目描述

暴力枚举 / SPFA / Bellman-ford / 奇怪的贪心 / 超神搜索 寻找一个从顶点 $1$ 所能到达的负环,负环定义为:一个边权之和为负的环。

输入输出格式

输入格式


**本题有多组数据** 第一行一个正整数 $T$ 表示数据组数,对于每组数据: 第一行两个正整数 $N, M$,表示图有 $N$ 个顶点,$M$ 条边 接下来 $M$ 行,每行三个整数 $a, b, w$,表示$a \rightarrow b$ 有一条权值为 $w$ 的边(若 $w<0$ 则为单向,否则双向)。

输出格式


共 $T$ 行。对于每组数据,存在负环则输出一行`YE5`(不含引号),否则输出一行`N0`(不含引号)。

输入输出样例

输入样例 #1

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

输出样例 #1

N0
YE5

说明

$n\le 2000$,$m\le 3000$,$-10000\le w \le 10000$,$T\le 10$。 建议复制输出格式中的字符串。 本题数据感谢 @[negiizhao](/user/5643) 的精心构造,请不要使用玄学算法。 本题数据有更新。