URI 1427 - The Scrooge Co Problem

The delivery company Scrooge Co. wants to establish a system to pay its employees the minimum money in their travels. The company has information about which the minimum cost to go from a location to another one is.

They ask you for getting a solution to compute the minimum amount of money that an employee will receive to go from one location to another one and which the route that he should use to arrive in is.

Input

The input begins with a single integer 1 ≤ C ≤ 99 on a line by itself, indicating the number of test cases following, each of them as described below.

For each test case, the first line has an integer 1 ≤ P ≤ 99, indicating the number of locations we consider for this case. The second line gives us the name of each location separated by a TAB, each name has at most 20 characters.The next P lines contain the minimum cost to go from one location to another one separated by a TAB, the first line have the costs between the first location and the rest, the second line are the costs between the second location and the rest, and so on. A cost is an integer -1 ≤ W ≤ 300, where -1 means that is too expensive a travel between the locations, and 0 is used to indicate the cost from a location to the same location. After the P lines there is an integer 1 ≤ R ≤ 99, indicating the number of routes that we have to consider. Following R lines containing the name of the employee, the start location and the end location. The locations names are case sensitive and the name of the employee has at most 30 characters.

Output

For each test case you should produce one or two outputs line. If a route between the locations exists, you will produce two lines, one with the cost and other with the path according to this format:

"Mr <employee name> to go from <orig name> to <dest name>, you will receive <minimum cost> euros"
"Path:<orig name> <locations separated by a blank> <dest name>"

If a route between the locations does not exist, you will produce one line, according to this format:

"Sorry Mr <employee name> you can not go from <orig name> to <loc name>"

If there are two possible minimal paths between A and B and both have intermediate vertices, the preference is to the path that appears before in the input, for example:

If the input is: A B C D E F, the path "A C D B" has more priority that the path "A E B" (since E appears after D) and the path "A D E B" has more priority that "A C F B" (because F appears after E). This analysis is done by looking the order of the intermediate vertices.

Sample Input	Sample Output
2 6 Ofi1 Ofi2 Ofi3 ofi4 ofi5 ofi6 0 4 1 -1 4 -1 4 0 -1 2 3 4 1 -1 0 -1 3 -1 -1 2 -1 0 -1 1 4 3 3 -1 0 2 -1 4 -1 1 2 0 1 emp1 Ofi1 ofi4 3 Murcia Alicante Albacete 0 3 -1 -1 0 4 -1 -1 0 2 Dofyl Murcia Albacete Dofyl Albacete Murcia	Mr emp1 to go from Ofi1 to ofi4, you will receive 6 euros Path:Ofi1 Ofi2 ofi4 Mr Dofyl to go from Murcia to Albacete, you will receive 7 euros Path:Murcia Alicante Albacete Sorry Mr Dofyl you can not go from Albacete to Murcia