The directed weighted graph is given. Using its weighted matrix, determine for each pair of vertices whether there exists a shortest path between them or not.
The shortest path may not exist for two reasons:
There is no way.
There is a way of arbitrarily small weight.
The first line contains the number of vertices n (1≤n≤100). The next n lines contains n numbers that describe the weighted matrix (j-th of the i-th row corresponds to the weight of the edge from vertex i to vertex j). The number 0 in this matrix represents no edge, and any other number — the existence of an edge of corresponding weight. All the numbers do not exceed 100 by absolute value.
Print n rows with n numbers: the j-th number in the i-th row must be 0 if the path from i to j does not exist, 1 if there is a shortest path, and 2 if there is a path of arbitrarily small weight.