CF402E.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.

你有一个大小为 $ n \times n $ 的矩阵 $ a $。我们将矩阵的行从上到下编号为 $ 1 $ 到 $ n $，列从左到右编号为 $ 1 $ 到 $ n $。用 $ a_{ij} $ 表示第 $ i $ 行与第 $ j $ 列交叉处的元素。

矩阵 $ a $ 满足以下两个条件：

• 对任意整数 $ i, j $（$ 1 \leq i, j \leq n $），均有不等式 $ a_{ij} \geq 0 $ 成立；
• 。

若对任意整数 $ i, j $（$ 1 \leq i, j \leq n $）均有 $ b_{ij} > 0 $，则称矩阵 $ b $ 是严格正的。你的任务是判断：是否存在某个整数 $ k \geq 1 $，使得矩阵 $ a^k $ 是严格正的。

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__i_1, _a__i_2, ..., a__in (0 ≤ a__ij ≤ 50). It is guaranteed that .

第一行包含一个整数 $ n $（$ 2 \leq n \leq 2000 $）——矩阵 $ a $ 的行数与列数。

接下来的 $ n $ 行描述了矩阵 $ a $ 的各行。第 $ i $ 行包含 $ n $ 个非负整数 $ a_{i1},\ a_{i2},\ \dots,\ a_{in} $（$ 0 \leq a_{ij} \leq 50 $）。保证满足 。

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

如果存在一个正整数 $k \geq 1$，使得矩阵 $a^k$ 是严格正的，则输出 "YES"（不带引号）。否则，输出 "NO"（不带引号）。