Same Distance Different Path

2 secs 1024 MB
RedSpica

問題文


頂点からなる完全無向グラフが与えられます.便宜上番目の頂点を頂点と呼びます.
また,各辺の長さは行列によって与えられ, 頂点と頂点を結ぶ辺の長さはです.

ここで以下の条件を満たす異なるつの単純パスが存在するかどうかを判定してください.

  • 頂点から頂点へのパスであって,グラフ上のそのつのパスの長さが等しい

より厳密には以下の条件を全て満たす異なるつの整数列が存在するかどうかを判定してください.

  • の各要素は以上以下の整数で,相異なる
  • の各要素は以上以下の整数で,相異なる
  • の項数をの項数をとすると,

ただし,つの数列が異なるとは,以下の条件のうち少なくともつを満たすときにいいます.

  • の項数との項数が異なる
  • ある整数が存在してとなる

制約


  • 入力される値はすべて整数である

入力


入力は以下の形式で標準入力から与えられます.





出力


条件を満たすものが存在するときはYesを, そうでないときはNoを出力せよ.

サンプル


入力1
3
0 1 3
1 0 2
3 2 0
出力1
Yes

つのパスとしてを取るとこれは条件を満たします.

入力2
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
出力2
Yes

つのパスとしてを取るとこれは条件を満たします. 他にも条件を満たすパスの組は複数存在します.

入力3
4
0 1 2 4
1 0 8 16
2 8 0 32
4 16 32 0
出力3
No

提出


Go (1.14)