Дано орієнтований граф. Визначити, чи є у ньому цикл негативної ваги.

Формат вхідних даних

У першому рядку міститься число \(N\) \((1 \le N \le 100)\) – кількість вершин графа.

У наступних \(N\) рядках знаходиться \(N\) чисел – матриця суміжності графа. Вага ребер за модулем менше 100000. Якщо ребра немає, відповідне значення дорівнює 100000.

Формат вихідних даних

У першому рядку виведіть "YES", якщо цикл негативної ваги існує, або "NO", інакше.

Приклад вхідних даних

3
100000 100000 -51
100  100000 100000
100000 -50  100000

Приклад вихідних даних

YES