A9437 | Strictly Positive Matrix

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}>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).