你有一个大小为 n × n 的矩阵 a。我们将矩阵的行从上到下编号为 1 到 n,将列从左到右编号为 1 到 n。我们用 aij 来表示第 i 行和第 j 列交集上的元素。
矩阵a满足以下两个条件:
- 对于任何数字 i, j (1 ≤ i, j ≤ n),以下不等式成立:aij ≥ 0;
- $$\sum_{i=1}^{n}a_{ii}>0$$。
如果对于任何数字 i, j (1 ≤ i, j ≤ n) 不等式 bij > 0 成立,则矩阵 b 严格为正。您的任务是确定是否存在这样的整数 k ≥ 1,即矩阵 ak 严格为正。
输入
第一行包含整数 n (2 ≤ n ≤ 2000) — 矩阵 a 中的行数和列数。
接下来的 n 行包含矩阵 a 的行的描述。第 i 行包含 n 个非负整数 ai1, ai2, ..., ain (0 ≤ aij ≤ 50)。保证$$\sum_{i=1}^{n}a_{ii}>0$$。
输出
如果存在正整数 k ≥ 1,使得矩阵 ak 严格为正,则打印“YES”(不带引号)。否则,打印“NO”(不带引号)。
示例
输入 #1
2 1 0 0 1
输出 #1
NO
输入 #2
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
输出 #2
YES