【模板】负环

题目描述

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

输入输出格式

输入格式


第一行一个正整数T表示数据组数,对于每组数据: 第一行两个正整数N M,表示图有N个顶点,M条边 接下来M行,每行三个整数a b w,表示a->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\leq 2000$$ $$m\leq 3000$$ $$-10000\leq w\leq 10000$$ $$T\leq 10$$ 建议复制输出格式中的字符串。 本题数据感谢@negiizhao的精心构造,请不要使用玄学算法 **本题数据有更新**