Animal Communication

Given M animals and an M×M matrix \(S\) representing the direct communication between them where \(S[i][j] = 1\) indicates that animal \(i\) can directly communicate with animal \(j\) (and \(S[i][i]=1\) for all \(i\)), determine if every pair of animals can communicate with each other either directly or indirectly.

Two animals can communicate indirectly if there exists a sequence of animals \(a_1, a_2, \dots, a_k\) such that each adjacent pair in the sequence can communicate directly. This problem can be solved using the Floyd-Warshall algorithm to compute the transitive closure of the communication graph.

inputFormat

The input is read from stdin and has the following format:

M
S[0][0] S[0][1] ... S[0][M-1]
S[1][0] S[1][1] ... S[1][M-1]
...
S[M-1][0] S[M-1][1] ... S[M-1][M-1]

Where (M) is the number of animals (1 ≤ M ≤ N) and each of the next M lines contains M integers (either 0 or 1) representing the communication matrix. It is guaranteed that (S[i][i] = 1) for all (i).

outputFormat

Output a single line to stdout containing either YES if every animal can communicate with each other (directly or indirectly) or NO otherwise.## sample

1
1

YES