You are given a directed weighted graph. Using its adjacency matrix, you need to determine for each pair of vertices whether there is a shortest path between them or not.
Comment: The shortest path may not exist for two reasons:
- There are no paths
- There are paths of arbitrarily small weight
Input
The first line of the input file contains a single number: N (1 <=N <=100) — the number of graph vertices. The next N lines contain N numbers each — adjacency matrix of the graph (the j-th number in the i-th line corresponds to the weight of the edge from vertex i to vertex j): the number 0 means no edge, and any other number — the presence of an edge of the corresponding weight. All modulo numbers do not exceed 100.
Output
Print N lines of N numbers. The j-th number in the i-th line must correspond to the shortest path from vertex i to vertex j. The number should be 0 if there is no path, 1 if there is a shortest path, and 2 if there are paths but there are paths of arbitrarily small weight.
Examples
| # |
Input |
Output |
| 1 |
5
0 1 2 0 0
1 0 3 0 0
2 3 0 0 0
0 0 0 0 -1
0 0 0 -1 0
|
1 1 1 0 0
1 1 1 0 0
1 1 1 0 0
0 0 0 2 2
0 0 0 2 2
|