SP15430 UCV2013B - Alice in Amsterdam, I mean Wonderland

这是一个鲜为人知的事实，爱丽丝曾住在阿姆斯特丹。像当时的许多孩子一样，她常去药店买一些药用蘑菇（那时还没有咖啡店）。通常，在普通的蘑菇中能够找到一种神奇的，它会产生强烈的幻觉。一次幻觉中，爱丽丝被带到了一个“仙境”，在那里发生了许多奇怪的事情。尤其让她感到费解的是，尽管很多地方看起来很熟悉，但城市的纪念碑之间的距离有时竟然是负数！不过，如果两个纪念碑之间的距离为零，意味着没有直接路径存在。然而，从某个纪念碑回到自身的环路距离可以是零，这表示它可以瞬间到达（就像现实一样），或是负数，就像普通路径一样。爱丽丝还记得看到过一些正数的环距离，但我们应该将这些情况视为零距离。 作为一个聪明的女孩，爱丽丝曾找到了解决如何找出任意两个纪念碑之间最短路径的方法。不幸的是，她恢复清醒后就将方法忘记了。她只记得有时自己可能会陷入一个负距离的循环路径中。在这种情况下，总会存在一条更便宜的路径能到达同一个纪念碑。这是少数几个令她完全理解的事情之一：你的路径会随着你无数次通过负循环而缩短，直至无限小。爱丽丝一直在想方设法重新弄清最佳路径，但始终无法做到。她不想再踏入幻觉，因为她已经保持清醒一年多了（对她来说，这真是件好事！）。你能帮助她吗？ 给定一个城市中的纪念碑列表以及它们之间的相对距离，找出一些纪念碑对之间的最短路径。

每个测试用例开始于一行包含 **N**，表示该测试用例中的纪念碑数量（1 ≤ **N** ≤ 100）。接下来的 **N** 行中每行包含一个字符串 **K** 和 **N** 个整数 **Kj**，它们用空格分隔。**K** 代表纪念碑的名字，最多由 20 个字母或数字组成。第 **i** 行的每个整数 **Kj**（0 ≤ **j** < **N**）表示从纪念碑 **i** 到纪念碑 **j** 的距离（-2^30 ≤ **Kj** ≤ 2^30）。接下来的一行将提供一个整数 **Q**（1 ≤ **Q** ≤ **N**^2）。接下来的 **Q** 行中，每行给出一对整数 (**U**, **V**)，表示要查询的起始和目标纪念碑（0 ≤ **U**, **V** < **N**）。输入的结束标志是一个值为 **N** = 0 的测试用例，而不应处理这种情况。

对于每个测试用例，输出一行 "Case #**tc**:"（不含引号），其中 **tc** 是测试用例的编号，从 1 开始。接下来的 **Q** 行应说明查询结果。如果最优路径的距离可以无限小，输出 "NEGATIVE CYCLE" 即可。在其他情况下，请按照 "**起点名称**-**终点名称**" 开头，接着给出实际结果。如果目标不可达，输出 "NOT REACHABLE"，否则输出整数形式的距离。 **本翻译由 AI 自动生成**