E. Строго положительная матрица
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У вас есть матрица 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