You are given a directed unweighted connected graph. You want to determine if it contains cycles.
Input: The first line contains one natural number n — number of vertices (0 ≤ n ≤ 1 111).
The next n lines contain the adjacency matrix of the graph. If the position (i, j) of the square matrix is 1, then the i-th and j-th edges are connected by edges, and if it is a zero, then they are not connected. In this case, the edge is directed from the i-th to the j-th edge of the graph, and the j-th and i-th edges are not connected by edges.
Output: The first line should contain YES if the graph contains a cycle and NO — otherwise.
Examples
| # |
Input |
Output |
| 1 |
8
0 1 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
|
YES |