An unweighted directed graph is defined by its adjacency matrix. It is required to construct its transitive closure, that is, a matrix in which the i-th row and j-th column contain 1 if it is possible to get from vertex i to vertex j, and 0 otherwise.
Input
The first line contains the number N (1<=N<=100) - the number of vertices in the graph. Next, the adjacency matrix of the graph is given: N lines contain N numbers 0 or 1 in each. The i-th number in the i-th line is always 1.
Output
It is necessary to output the graph's transitive closure matrix in a format similar to the format of the adjacency matrix.
|
Enter |
Output |
|
4
|
1 1 1 0
1 1 1 0
1 1 1 0
1 1 1 1
|