← 返回题目列表

Codeforces · 402/E

E. 严格正矩阵

中文机器翻译题面 查看原题

你有一个大小为 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