| Codeforces Round 236 (Div. 2) |
|---|
| Закончено |
У вас есть матрица 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 является строго положительной.
В первой строке задано целое число n (2 ≤ n ≤ 2000) — количество строк и столбцов в матрице a.
В следующих n строках задано описание строк матрицы a. В i-ой строке задано n целых неотрицательных чисел ai1, ai2, ..., ain (0 ≤ aij ≤ 50). Гарантируется, что .
Если существует целое число k ≥ 1, такое, что матрица ak является строго положительной, выведите «YES» (без кавычек). Иначе, выведите «NO» (без кавычек).
2
1 0
0 1
NO
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
