Competitions

# Shortest paths - interesting graph problems

# Sum on a tree reversed

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.

#### Input

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`

- the distances between the pairs of vertices.^{9}

#### Output

Print **YES**, if such tree exists, and **NO** otherwise.

Input example #1

3 0 5 1 5 0 6 1 6 0

Output example #1

YES