ADACYCLE  Ada and Cycle
Ada the Ladybug is on a trip in Bugindia. There are many cities and some unidirectional roads connecting them. Ada is wondering about the shortest path, which begins in a city and ends in the same city. Since Ada likes short trips, she asked you to find the length of such path for each city in Bugindia.
Input
The first line will contain 0 < N ≤ 2000, the number of cities.
Then N lines follow, each containing N integers 0 ≤ H_{ij} ≤ 1. One means, that there is a road between i and j (zero means there isn't a road).
Output
Print N lines, the length of shortest path which begins in city i and ends in city i. If the path doesn't exist, print "NO WAY" instead.
Example Input
5 0 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0
Example Output
2 2 1 2 NO WAY
Example Input
5 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0
Example Output
2 5 5 5 2
hide comments
morass:
20160915 11:54:25
@Harsh Rumalwala: Good day to you! Well In my opinion, your algorithm is O(N*E+N^2) [E is number of edges], where E might be N^2 in worstcase ... so it is O(N^3) in worst case. Isn't that so? :O 

Harsh Rumalwala:
20160915 07:19:28
Why O(n^2) solution is resulting in TLE while it should easily pass under the given time constraints? 

morass:
20160913 16:05:56
@[Rampage] Blue.Mary: Good day to you man! Nope, it is expected worst complexity "with some improvisation" if you understand me :) 

[Rampage] Blue.Mary:
20160913 16:00:29
What's the expected complexity? Is a (strictly) O(n^2) algorithm required?

Added by:  Morass 
Date:  20160913 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 