Star Routes

Space travelers have found information about routes between star gates. Using the gates, it is possible to travel to another world through space hypertunnels. The routes between gates, which exist in different worlds, are represented by matrices. All gates are numbered 1 \leq i \leq 100. The route matrix has $1$ in the $(i,j)$ position if there is a direct route from gate $i$ to gate $j$.

All other positions contain $0$. The existence of a direct route from gate $i$ to gate $j$ does not guarantee the existence of a route from $j$ to $i$. However, there is always $1$ in the $(i,i)$ position.

The problem is as follows. Using the given route matrix, you have to find the advanced route matrix, which shows all possible routes. This matrix provides information about whether gate $k$ is reachable from any other gate $i$. That is, if a route from gate $i$ to gate $j$ exists and a route from gate $j$ to gate $k$ exists, then a route from $i$ to $k$ exists as well. The existence of a route is also represented by $1$ in the appropriate matrix position.

So, an advanced route can be not only direct but can also contain intermediate gates.