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 n 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 n (1 ≤ n ≤ 1000). Then given the matrix itself: n lines contain n nonnegative integers, not exceeding 10^9
- the distances between the pairs of vertices.
Print YES, if such tree exists, and NO otherwise.