Module: Floyd's algorithm

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:

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.

 

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