Требуется построить его транзитивное замыкание, то есть матрицу, в которой в i-й строке и j-м столбце находится 1, если от вершины i можно добраться до вершины j, и 0 – иначе.
В первой строке входного файла INPUT.TXT записано целое число N (1 ≤ N ≤ 100) – число вершин в графе. Далее задана матрица смежности графа: в N строках даны по N чисел 0 или 1 в каждой. i-е число в i-й строке всегда равно 1.
В выходной файл OUTPUT.TXT выведите матрицу транзитивного замыкания графа в формате, аналогичным формату матрицы смежности.
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
1 1 0 0
0 1 1 0
1 0 1 0
0 0 1 1 | 1 1 1 0
1 1 1 0
1 1 1 0
1 1 1 1 |
