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
glydon:
20221015 04:21:28
I was facing TLE in the problem until I realized that when you are getting demanded source as an adjacent of someone,


cpchef7:
20220124 20:38:41
Got an AC, in first time for first time 

rushi2001:
20210520 00:22:48
Simple bfs from every point to find shortest distance to itself .


ktkrsk:
20200605 17:13:08
Is it solvable in C#? Im getting TLE with BFS with Adj list and fast IO(StringBuilder etc). Or do I need to use the SCC? 

mr_dot_convict:
20190603 10:26:07
The time limit shown is 3s but I found none of the accepted solutions below 3s. A naive bfs solution without any optimizations(except adjacency list if you call it an optimization) works well too but in approx. 5s.


snjumaheshwari:
20190525 16:19:16
Solved but not satisfied. Changed cout (with fast i/o) to printf and worked.


vjvjain0:
20190520 00:12:13
Got to learn applications of bfs and dfs. Sad that same logic which passed in CPP won't pass in Java :( 

dschen:
20190318 16:09:33
why I always got Segmentation Fault ...


ameyanator:
20180220 17:56:10
To get an AC you need to optimize your code so that you only consider those edges that the current node stems to. You should know this before or preprocess it. 

anurag_tangri:
20171109 19:38:05
i am getting TLE please give some hint ! 
Added by:  Morass 
Date:  20160913 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 