Рассмотрим квадратную матрицу $$$a$$$ размера $$$n$$$, состоящую только из нулей и единиц.
Выполним над ней следующий алгоритм: пока существуют такие индексы $$$i$$$, $$$j$$$, $$$k$$$ (не обязательно различные), что $$$a[i][j]=1$$$, $$$a[j][k]=1$$$, $$$a[i][k]=0$$$, заменяем $$$a[i][k]$$$ на $$$1$$$. Получившуюся в итоге матрицу назовём транзитивным замыканием матрицы $$$a$$$.
Для заданной матрицы $$$a$$$ найдите такую матрицу $$$b$$$, что она содержит минимальное количество единиц, а её транзитивное замыкание совпадает с транзитивным замыканием матрицы $$$a$$$.
Первая строка входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 100$$$).
В следующих $$$n$$$ строках записаны по $$$n$$$ чисел 0 или 1 — элементы матрицы $$$a$$$.
Выведите искомую матрицу $$$b$$$. Если есть несколько верных ответов, выведите любой.
31 1 11 0 10 0 1
0 1 0 1 0 1 0 0 1
Матрицы из примера имеют следующее транзитивное замыкание:
1 1 1
1 1 1
0 0 1
