You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给出一个矩阵 $A$，问是否存在一个正整数 $k$ 使得 $A^k$ 的所有元素都是正数。

输入格式

第一行包含整数 $n$ ( $2<=n<=2000$ ) — 矩阵 $a$ 中的行数和列数。

接下来的 $n$ 行包含矩阵 $a$ 每行的描述。第 $i$ 行 $n$ 个数字分别为 $a_{i1},a_{i2},...,a_{in}$ ( $0<=a_{ij}<=50$ )。

输出格式

如果有一个正整数 $k>=1$ ，使得矩阵 $a^{k}$ 严格为正数，请打印 “YES” （不带引号）。否则，打印“NO”（不含引号）。

样例 #1

样例输入 #1

2
1 0
0 1

样例输出 #1

NO

样例 #2

样例输入 #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

测试点约束

$2\leq n\leq2000,0\leq a_{i,j}\leq 50,\sum_{i=1}^na_{i,i}>0$