AT_kupc2015_c 最短経路

[problemUrl]: https://atcoder.jp/contests/kupc2015/tasks/kupc2015_c ある単純有向グラフにおける任意の二頂点間の最短距離に関する条件が与えられる. その条件を満たす有向グラフが存在するかどうか判定せよ.

入力は以下の形式で標準入力から与えられる． > $ 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`を出力せよ.