Рассмотрим квадратную матрицу размера $$$n \times n$$$, состоящую из неотрицательных целых чисел. Матрица симметрична относительно главной диагонали, которая, в свою очередь, содержит лишь нули. Такая матрица называется деревянной, если существует такое неориентированное дерево $$$T$$$ на $$$n$$$ вершинах с рёбрами положительных длин, что в каждой ячейке матрицы $$$(i, j)$$$ записано расстояние между вершинами $$$i$$$ и $$$j$$$ в этом дереве.
Дана матрица. Проверьте, является ли она деревянной.
В первой строке дано целое число $$$n$$$ — размер матрицы ($$$1 \le n \le 1000$$$). В каждой из следующих $$$n$$$ строк задано по $$$n$$$ целых чисел $$$d_{i,j}$$$ — элементы матрицы ($$$0 \le d_{i,j} \le 10^9$$$). Матрица симметрична относительно главной диагонали. На главной диагонали стоят нули, а вне её — строго положительные целые числа.
Выведите «Yes» или «No» в зависимости от того, является ли матрица деревянной. Регистр букв не важен.
30 1 31 0 23 2 0
Yes
30 1 31 0 13 1 0
No