Path Finding

Interview

Time limit1sMemory limit256 MB

Summary

Decide for every ordered pair of vertices in a directed graph with up to 100 vertices whether a path of at least one edge connects them.

Level: Easy3 of 10
Topics: Graph, Dynamic programming
Solved: No attempts yet

Problem

You are given an unweighted directed graph $G$ . Write a program that decides, for every pair of vertices $(i, j)$ , whether a path of positive length runs from $i$ to $j$ .

A path of positive length uses at least one edge. So the answer for $(i, i)$ is 1 only when some path leaves $i$ and comes back to $i$ .

Input

The first line contains the number of vertices $N$ ( $1 \le N \le 100$ ).

Each of the next $N$ lines contains one row of the adjacency matrix. If the $j$ -th number on the $i$ -th line is 1, an edge goes from $i$ to $j$ ; if it is 0, no such edge exists. The $i$ -th number on the $i$ -th line is always 0.

Output

Print the answer as an adjacency matrix over $N$ lines. If a path of positive length runs from vertex $i$ to vertex $j$ , print 1 as the $j$ -th number on the $i$ -th line, otherwise print 0. Separate the numbers on a line with a single space.

Examples2

Example 1
Input
```
3
0 1 0
0 0 1
1 0 0
```
Expected output
```
1 1 1
1 1 1
1 1 1
```

Example 2

Input

7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0

Expected output

1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 0 0 0 0 0
1 0 1 1 1 1 1
1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 1 0 0 0 0