Strictly Positive Matrix

给出一个矩阵 $A$，问是否存在一个正整数 $k$ 使得 $A^k$ 的所有元素都是正数。 $2\leq n\leq2000,0\leq a_{i,j}\leq 50,\sum_{i=1}^na_{i,i}>0$

You have matrix $ a $ of size $ n×n $ . Let's number the rows of the matrix from $ 1 $ to $ n $ from top to bottom, let's number the columns from $ 1 $ to $ n $ from left to right. Let's use $ a_{ij} $ to represent the element on the intersection of the $ i $ -th row and the $ j $ -th column. Matrix $ a $ meets the following two conditions: - for any numbers $ i,j $ ( $ 1<=i,j<=n $ ) the following inequality holds: $ a_{ij}>=0 $ ; - . Matrix $ b $ is strictly positive, if for any numbers $ i,j $ ( $ 1<=i,j<=n $ ) the inequality $ b_{ij}&gt;0 $ holds. You task is to determine if there is such integer $ k>=1 $ , that matrix $ a^{k} $ is strictly positive.

The first line contains integer $ n $ ( $ 2<=n<=2000 $ ) — the number of rows and columns in matrix $ a $ . The next $ n $ lines contain the description of the rows of matrix $ a $ . The $ i $ -th line contains $ n $ non-negative integers $ a_{i1},a_{i2},...,a_{in} $ ( $ 0<=a_{ij}<=50 $ ). It is guaranteed that .

If there is a positive integer $ k>=1 $ , such that matrix $ a^{k} $ is strictly positive, print "YES" (without the quotes). Otherwise, print "NO" (without the quotes).

2
1 0
0 1

NO

5
4 5 6 1 2
1 2 3 4 5
6 4 1 2 4
1 1 1 1 1
4 4 4 4 4

YES