ADACYCLE - Ada and Cycle

no tags 

Ada the Ladybug is on a trip in Bugindia. There are many cities and some uni-directional 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 ≤ Hij ≤ 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
vjvjain0: 2019-05-20 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: 2019-03-18 16:09:33

why I always got Segmentation Fault ...

I thought I hadn't any invalid access...
and my MAX_N was set as 2200...

Last edit: 2019-03-18 16:17:39
ameyanator: 2018-02-20 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: 2017-11-09 19:38:05

i am getting TLE please give some hint !

Fendy: 2017-02-25 11:21:24

Hi @morass, does your testcases covers the worst case? Since I've seen few BFS algorithm could solve this problem.
Thank you.

morass: 2016-09-17 07:43:56

@Harsh Rumalwala Thanx man! Great to see you've solved it!

Harsh Rumalwala: 2016-09-17 03:05:48

@morass : Thanks for replying .Decreased the complexity of the solution and got AC. Good question.

Last edit: 2016-09-17 03:33:56
morass: 2016-09-15 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 worst-case ... so it is O(N^3) in worst case. Isn't that so? :O

Harsh Rumalwala: 2016-09-15 07:19:28

Why O(n^2) solution is resulting in TLE while it should easily pass under the given time constraints?

morass: 2016-09-13 16:05:56

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


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