The problem 2157 Sum for a given weighted tree asks to find the total length of all paths in the tree.
Now we propose you to solve the inverse problem. Given a distance matrix between all the nodes of a tree with vertices. Determine whether this matrix is a matrix of pairwise distances between all vertices of weighted tree. All the weights of the tree edges should be positive integers.
The first line contains the size of the matrix (1 \le n \le 1000). Then the matrix itself is given: lines contain nonnegative integers, not exceeding 10^9 - the distances between the pairs of vertices.
Print YES, if such tree exists, and NO otherwise.
Example 1