Transitive Closure of a Directed Graph

Given a directed graph with n nodes represented by an n × n adjacency matrix A = (a_ij), compute its transitive closure.

The adjacency matrix is defined as follows:

$$ a_{ij}=\begin{cases}1, & \text{if there is a direct edge from } i \text{ to } j,\\0, & \text{if there is no direct edge from } i \text{ to } j.\end{cases}$$

The transitive closure of the graph is an n × n matrix B = (b_ij), where

$$ b_{ij}=\begin{cases}1, & \text{if there exists a sequence of edges (direct or indirect) from } i \text{ to } j,\\0, & \text{otherwise}.\end{cases}$$

inputFormat

The first line of input contains an integer n representing the number of nodes in the graph.

The following n lines each contain n integers separated by spaces, representing the rows of the adjacency matrix A. It is guaranteed that the graph contains no self-loops (i.e. all diagonal elements of the matrix are 0).

outputFormat

Output the transitive closure of the graph as an n × n matrix. Each of the n lines should contain n integers separated by a single space.

sample

1
0

0

</p>