Transitivity of directed graph

The directed graph is called transitive, if for its any three distinct vertices $u,v$ and $w$ from the fact that there are edges from $u$ to $v$ and from $v$ to $w$ it follows that there is an edge from $u$ to $w$.

Check that the given directed graph is transitive.

Input

The first line contains the number of vertices $n(1\le n\le 100)$ in the graph. The next $n$ lines contain the adjacency matrix of the graph.

Output

Print "YES" if graph is transitive and "NO" otherwise.

Examples