Задача №112575. Существование графа

Пусть G — взвешенный неориентированный граф с N вершинами и M рёбрами. Веса рёбер — положительные целые числа. Длину пути P в графе G определим как сумму весов рёбер в P . Расстоянием d ij будем называть длину наикратчайшего пути в G от v i до v j (для i , j = 1, 2, ..., N ). Если такого пути нет, то d ij = ∞ . Матрица расстояний графа с N вершинами — матрица D (размерности N × N ), содержащая значения d ij . В случае d ij = ∞ соответствующий элемент матрицы равен - 1 . Например, матрица для изображённого графа выглядит так:

Вам дана квадратная матрица D с целыми числами. Напишите программу, определяющую, является ли D матрицей расстояний какого-нибудь графа.

Входные данные

Первая строка содержит целое число N (1 ≤ N ≤ 200) . Следующие N строк описывают матрицу D . Каждая строка содержит N целых чисел в диапазоне [ - 1;1000] , разделённых пробелами.

Выходные данные

Если данная матрица соответствует матрице расстояний определённого графа, то выведите YES , иначе выведите NO .

Примеры
Входные данные
4
0 1 1 -1
1 0 1 -1
1 1 0 -1
-1 -1 -1 0
Выходные данные
YES
Входные данные
3
0 1 3
1 0 1
3 1 0
Выходные данные
NO
Сдать: для сдачи задач необходимо войти в систему