問題文
给出了简单有向图中任意两个顶点之间的最短距离的条件。确定是否存在满足该条件的有向图。
入力
输入是按以下格式从标准输入给出的。
T
N_1
a_{11} ... a_{1N_1}
a_{21} ... a_{2N_1}
:
a_{N_1 1} ... a_{N_1 N_1}
:
:
N_T
a_{11} ... a_{1N_T}
a_{21} ... a_{2N_T}
:
a_{N_T 1} ... a_{N_T N_T}
输入由多个测试用例组成。1 行包含一个表示测试用例数量的整数。 给出 T ( 1 \leq T \leq 30)。 随后 T 测试用例按顺序给出。 在测试用例 t ( 1 \leq t \leq T 中,第一行包含一个表示图中顶点数的整数。 给出 N_t ( 1 \leq N_t \leq 30)。 继续 每条 N_t 行都有 给定 N_t 由空格分隔的整数, i 线 j 第一个整数 a_{ij} (1 \leq i,j \leq N_t, -1 \leq a_{ij} \leq 10000 ) 是 对于 -1,顶点 表示没有到达 i 到顶点 通往 j 的路由,否则顶点 到 i 到顶点 通往 j 的最短距离是 a_{ij} 。
出力
如果存在满足约束条件的有向图,则YES,如果没有
输出NO。
入力例
4 3 0 2 3 4 0 1 3 2 0 3 0 2 4 4 0 1 3 2 0 2 0 -1 -1 0 2 0 -1 -1 1
出力例
YES NO YES NO