Сума на дереві навпаки

У задачі 2157 Сума для заданого дерева потрібно знайти загальну довжину всіх шляхів у дереві.

Тепер ми пропонуємо вам вирішити обернену задачу. Дано матрицю відстаней між усіма вершинами дерева з n вершинами. Потрібно визначити, чи може ця матриця бути матрицею попарних відстаней між усіма вершинами зваженого дерева. Усі ваги ребер дерева повинні бути натуральними числами.

Вхідні дані

Перший рядок містить розмір матриці n (1 ≤ n ≤ 1000). Далі подано матрицю відстаней: у n рядках розміщено n цілих невід'ємних чисел, що не перевищують 10^9 - відстані між парами вершин.

Вихідні дані

Виведіть YES, якщо таке дерево існує, і NO інакше.

Приклади