Given a directed graph. Determine if it has a negative weight cycle.
Input
The first line contains the number N (1 <= N <= 100) – the number of graph vertices. The next N lines contain N numbers each – graph adjacency matrix. Edge weights modulo less than 100000. If there is no edge, the corresponding value is 100000.
Output
On the first line print "YES" if the cycle exists, or "NO" otherwise.
Examples
| # |
Input |
Output |
| 1 |
3
100000 100000 -51
100 100000 100000
100000 -50 100000
|
YES |