Напомним, что ориентированный граф называется транзитивным, если для любых трех различных вершин u, v и w из того, что из u в вершину v ведет ребро и из вершины v в вершину w ведет ребро, следует, что из вершины u в вершину w ведет ребро.
Проверьте, что заданный ориентированный граф является транзитивным.
Входные данные
Сначала вводится число n ( 1≤n≤100 ) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.
Выходные данные
Выведите «YES», если граф является транзитивным, и «NO» в противном случае.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
|
YES
|