В задаче 2157 Сумма для заданного дерева следует найти суммарную длину всех путей в дереве.
Сейчас мы предлагаем Вам решить обратную задачу. Задана матрица расстояний между всеми вершинами дерева с n вершинами. Необходимо определить, может ли эта матрица быть матрицей попарных расстояний между всеми вершинами взвешенного дерева. Все веса ребер дерева должны быть натуральными числами.
Первая строка содержит размер матрицы n (1 ≤ n ≤ 1000). Далее следует матрица расстояний: в n строках расположены n целых неотрицательных чисел, не превосходящих 10^9
- расстояния между парами вершин.
Вывести YES, если такое дерево существует, и NO иначе.