問題文

$N$頂点からなる完全無向グラフが与えられます．便宜上$i$番目の頂点を頂点$i$と呼びます．
また，各辺の長さは$N \times N$行列$D$によって与えられ， 頂点$i$と頂点$j$を結ぶ辺の長さは$D_{i,j}$です．

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

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

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

• $A$の各要素は$1$以上$N$以下の整数で，相異なる
• $B$の各要素は$1$以上$N$以下の整数で，相異なる
• $A_1=B_1=1$
• $A$の項数を$n$，$B$の項数を$m$とすると，$A_n=B_m=N$
• $\sum^{n-1}_{i=1}D_{A_i,A_{i+1}} = \sum^{m-1}_{i=1}D_{B_i,B_{i+1}}$

ただし，$2$つの数列$A,B$が異なるとは，以下の条件のうち少なくとも$1$つを満たすときにいいます．

• $A$の項数と$B$の項数が異なる
• ある整数$i$が存在して$A_i \neq B_i$となる

制約

• $2 \leq N \leq 2 \times 10^2$
• $0 \leq D_{i,j} \leq 10^5$
• $i=j \Rightarrow D_{i,j}=0$
• $i \neq j \Rightarrow D_{i,j}>0$
• $D_{i,j}=D_{j,i}$
• 入力される値はすべて整数である

入力

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

出力

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

サンプル

3
0 1 3
1 0 2
3 2 0

Yes

$2$つのパスとして$\{1,3\}$と$\{1,2,3\}$を取るとこれは条件を満たします．

4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

Yes

$2$つのパスとして$\{1,2,3,4\}$と $\{1,3,2,4\}$を取るとこれは条件を満たします． 他にも条件を満たすパスの組は複数存在します．

4
0 1 2 4
1 0 8 16
2 8 0 32
4 16 32 0

No