SP70 RELATS1 - Relations

给定一个有向图，其边用关系符号 `` 和`=`标记。对于非负整数 $k$，$k$ -正确的 $G$ -标记是从 $G$ 的顶点到区间 $[0,k]$ 的整数的映射，使得每条边末端的数字都满足边的标记所描述的关系。我们假设关系符号左侧的元素是分配给初始顶点的数字。计算存在 $k$ -正确 $G$ 标记的最小 $k$，或验证任何 $k$ 都不存在此类标记。

输入文件的第一行包含一个不大于 $10$ 的正整数 $d$。$d$ 表示接下来有多少组数据集。每组数据集为 $d$ 后面的连续两行。在第一行中有两个整数 $n$ 和 $m$ 由单个空格分隔。数字 $n$ 是 $G$ 的顶点数，$m$ 是 $G$ 的边数。数字 $n$ 和 $m$ 满足 $1\le n\le1000,0 \le m\le10000$。顶点用从 $1$ 到 $n$ 的整数编号，并由这些数字标识。图中没有平行边和自循环。（两个不同的边 $u_1\rightarrow v_1$ 和 $u_2\rightarrow v_2$ 是平行的，如果 $u_1=u_2$ 且 $v_1=v_2$。）第二行有 $3\times m$ 个整数，由单个空格分隔。在位置 $3\times i-2$ 和 $3\times i-1$,$1\le i\le m$ 的数字分别是第 $i$ 条边的结尾、开始和结束，而位置在 $3\times i$ 的数字是集合 ${-1,0,1}$ 中的数字，它是第 $i$ 条边的标签：$-1$ 表示``。

对于第 $i$ 个数据集 $1\le i\le d$，如果任何 $k$ 或最小整数 $k$ 不存在正确的标记，则你的程序应该在输出文件的第 $i$ 行中输出一个单词 `NO`。 ### 输入输出样例 #### 输入 #1 ``` 4 4 4 1 2 -1 2 3 0 2 4 -1 3 4 -1 2 2 1 2 -1 2 1 -1 2 2 1 2 -1 2 1 1 3 3 1 2 0 3 2 0 3 1 0 ``` #### 输出 #1 ``` 2 NO 1 0 ```