У вас есть матрица a размера n × n. Строки матрицы пронумеруем от 1 до n сверху вниз, столбцы матрицы пронумеруем от 1 до n слева направо. Обозначим за aij элемент, находящийся пересечении i-й строки и j-го столбца.
Матрица a удовлетворяет следующим двум условиям:
- для любых чисел i, j (1 ≤ i, j ≤ n) верно неравенство aij ≥ 0;
-
.
Матрица b называется строго положительной, если для любых чисел i, j (1 ≤ i, j ≤ n) верно неравенство bij > 0. Вам необходимо определить, существует ли такое целое число k ≥ 1, что матрица ak является строго положительной.
Выходные данные
Если существует целое число k ≥ 1, такое, что матрица ak является строго положительной, выведите «YES» (без кавычек). Иначе, выведите «NO» (без кавычек).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 0
0 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
|
YES
|