UCV2013B - Alice in Amsterdam, I mean Wonderland

no tags 

This is a fact that not many people know, but Alice lived in Amsterdam. Yes, there you go. And as many kids of the time, she used to go for some medicinal mushrooms to the drug store (the pharmacies, the coffee shops didn't exist yet). Usually, between the regular mushrooms, a magical one could be found, producing as expected, deep and vivid hallucinations. During one of those hallucinations, Alice was transported to a "wonderland", where many weird things happened. One thing was particularly dazzling for her: even though everything looked pretty familiar, the distance between monuments of the city was sometimes negative!!! Although, zero distance between two different monuments means a direct path doesn't exist. A loop from a given monument right back to it can be of length zero (with means that it can be reached instantly like in real life) or negative, like for regular paths. Alice also thought that she saw some positive distances for loops, but we should treat those cases as zero distance.


Now, as a very smart girl as she is, she figured out a way to find the shortest path between any two monuments. Unfortunately, as expected, Alice forgot it when she got sober again. She was only able to remember that, in some cases, she could get stuck in a cycle path with negative distance. In such cases, there will always be a cheaper path to get to the same monument. This was one of the few things that had perfect sense for her: Your shortest path will be shorter if you take that cycle again and again, to infinity. Alice, has been trying to figure optimal distances all over again, but she can't. She doesn't want to trip again, she has been clean for longer than a year (good for her!!). Would you be so kind to help her?


Given a list of monuments in a city, and their relative distances, find the shortest paths between some pairs of monuments.

Input

Each case, starts with one line containing N, the number of monuments in the test case (1 <= N <= 100). Next N lines will each contain one string K and N integers Kj, separated by single spaces. K is a name of a monument and will consist of at most 20 alphanumeric characters. Each integer Kj (0 <= j < N) in line i describes the distance from monument i to j (-2^30 <= Kj <= 2^30). Next line will contain a single integer Q (1 <= Q <= N^2). It will be followed by Q lines, each with a pair of integers (U, V), indicating the start and destination monument for the path that is queried (0 <= U, U < N).
End of the input is indicated by a test case with N = 0 and should not be processed.

Output

For each test case, print a line "Case #tc:" (without quotes), where tc is the case number, starting from 1. Next Q lines should describe query results. If the optimal distance can be infinitely small, print only "NEGATIVE CYCLE". In other cases, start the line with "start_name-destination_name" followed by the actual result. If the destination can't be reached, print "NOT REACHABLE", otherwise print the integer distance.

Example

Input:
2
Nieuwkerk -1 1
Oudekerk 1 0
4
0 0
0 1
1 1
1 0
3
Nieuwkerk 0 -5 0
Oudekerk 10 0 0
Pierteck -100 -100 0
9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
0 Output: Case #1:
NEGATIVE CYCLE
NEGATIVE CYCLE
NEGATIVE CYCLE
NEGATIVE CYCLE
Case #2:
Nieuwkerk-Nieuwkerk 0
Nieuwkerk-Oudekerk -5
Nieuwkerk-Pierteck NOT REACHABLE
Oudekerk-Nieuwkerk 10
Oudekerk-Oudekerk 0
Oudekerk-Pierteck NOT REACHABLE
Pierteck-Nieuwkerk -100
Pierteck-Oudekerk -105
Pierteck-Pierteck 0
 

hide comments
Jose Sanchez: 2013-07-26 20:22:08

thanks @Jacob Plachta. i got acc

Rocker3011: 2013-07-25 22:30:16

What the comment below Miguel says is wrong, as the graph can be disconected, the negative cycle he states is wrong, the whole graph doesn't get negative cycle if you find one.

Costed me about all my W.A, needed help to find such a silly mistake. Also i did not take in account many things that are said in the comments and managed accepted. So, do not read the comments... just code :)

Last edit: 2013-07-25 22:33:25
Miguel Oliveira: 2013-07-25 20:49:58

I only output NEGATIVE CYCLE if the negative cycle is reachable by U. Since Jacob has his solution accepted, it seems there is no such case in the test data.

Jacob Plachta: 2013-07-25 02:30:42

1. Output NEGATIVE CYCLE for all of a test case's queries if there's a negative cycle anywhere in the graph.
2. If the distance from a node to itself is given as being positive, treat is as 0 instead.

Shaka Shadows: 2013-07-24 19:54:51

I got AC in this problem, but making an assumption not said in the statement. I've set distance from i to i = 0, despite the corresponding input value. I think that should be somehow in the description. I got a lot of WA due to that.

Shaka Shadows: 2013-07-24 14:42:47

I think that problem statement is not totally clear about negative cycles existence. When exactly should I report their existence in path from u to v?

Last edit: 2013-07-24 15:24:58
Miguel Oliveira: 2013-07-23 23:01:33

I always enjoy problems involving negative cycles :)

I think you missed some words while copy pasting:
- "indicating the distance to calculate. (0 <= U, V <= N)" should be "(0 <= U, V < N)".
- Kj's part is wrong in the statement. My AC code assumes Kj < 2^29.

Shaka Shadows: 2013-07-23 22:46:32

Input limits are not given and they should be.


Added by:Hector Navarro
Date:2013-07-22
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Local UCV 2013. Ignacio Calderón