ROHAAN - Defend The Rohan

Kingdom of Rohan is under attack! There are N vital army stations. King will decide what army should be guarding what station, to get the best strategic advantage against Sauron attacks. All armies are already in some stations, but not necessarily the stations required by the king. As a result armies will have to be moved. Distances between any pair of stations are known. They are not necessarily symmetrical, because road from station A to B could be different than road from B to A. When a army moves, it doesn't have to take a direct road and instead can choose to cross other stations, if that results in a shorter path.

Given the distances between stations and king's relocation orders, find the minimum total travel distance for all the armies.

Input

First line contains an integer T, number of test cases. Then the description of T test cases follow. Each test case starts with an integer N, which is the total number of army stations. Next N lines have N integers each, description of distances. b'th integer on line a is the distance from station a to station b. Description of kings orders follows. In a first line, a single integer R, number of orders. Next R lines will contain two integers s and d each, describing an order to move an army from station s to d.

Constrains:

1 <= T <= 50

1 <= N, R <= 50

1 <= distance <= 10^6

1 <= s, d <= N

Output

Print a single line for each test case. A string "Case #t: " without quotes, where t is the number of test case, starting from 1. Following the string, you must print the total distance armies must travel during relocation.

0 <= total distance <= 10^7

Example

Input:
1
3
0 1 1
1 0 1
1 9 0
2
2 1
3 2

Output:
Case #1: 3

Added by:Shenbaga Prasanna
Date:2013-06-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own

hide comments
2021-09-27 20:39:53
easy peasy lemon squeezy
2021-05-11 18:50:00
Please Some one explain given testcase and what is b'th integer.
2019-10-20 09:14:10
Why the fuck they make us write "case #i : "

Last edit: 2019-11-19 18:15:12
2019-03-09 20:17:29
mammadbastar ejdeha dareh miad
2019-03-04 15:35:30
ba tashakor az ostade azizam kianoosh abbasi
2018-12-12 07:16:04
jozve badihijate;)
2018-03-30 13:16:10
Perfect Application of Floyd Warshall Algorithm :)!
2013-07-14 15:48:23 biQar
I think the Time Limit is very strict for Java solutions. Please check the Time Limit for Java. I have submitted a code in Java which will take the input by using "BufferedReader" and print a garbage output. I got TLE for that instead of Wrong Answer!
-(prassi)-TL Modified to Comfort JAVA solutions. You can resubmit your solution
-(Reply) Thank you :)

Last edit: 2013-07-15 03:52:33
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.