Ma trận dương chặt

Cho ma trận vuông $a$ kích thước $n\times n$. Ký hiệu $a_{ij}$ là phần tử nằm ở giao của hàng $i$ và cột $j$ (các hàng đánh số từ $1$ đến $n$ từ trên xuống, các cột đánh số từ $1$ đến $n$ từ trái sang).

Ma trận $a$ thoả mãn hai điều kiện:

• $a_{ij}\ge 0$ với mọi $i,j$;
• $\sum _{i=1}^n{a}_{ii}>0$, tức là tổng các phần tử trên đường chéo chính là số dương.

Lũy thừa $a^k$ được định nghĩa là tích của $k$ bản sao của $a$ theo phép nhân ma trận thông thường. Một ma trận $b$ được gọi là dương chặt nếu $b_{ij}>0$ với mọi $i,j$.

Hãy xác định xem có tồn tại số nguyên $k\ge 1$ sao cho $a^k$ là ma trận dương chặt hay không.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số hàng và số cột của ma trận.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa $n$ số nguyên không âm $a_{i1},a_{i2},\dots ,a_{in}$.

Dữ liệu ra

In ra YES nếu tồn tại số nguyên $k\ge 1$ sao cho $a^k$ dương chặt, ngược lại in ra NO.

Ràng buộc

• $2\le n\le 2000$
• $0\le a_{ij}\le 50$
• $\sum _{i=1}^n{a}_{ii}>0$

Ví dụ