

The Shortest PathTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4042 Accepted Submission(s): 1375 Problem Description There are N cities in the country. Each city is represent by a matrix size of M*M. If city A, B and C satisfy that A*B = C, we say that there is a road from A to C with distance 1 (but that does not means there is a road from C to A). Now the king of the country wants to ask me some problems, in the format: Is there is a road from city X to Y? I have to answer the questions quickly, can you help me? Input Each test case contains a single integer N, M, indicating the number of cities in the country and the size of each city. The next following N blocks each block stands for a matrix size of M*M. Then a integer K means the number of questions the king will ask, the following K lines each contains two integers X, Y(1based).The input is terminated by a set starting with N = M = 0. All integers are in the range [0, 80]. Output For each test case, you should output one line for each question the king asked, if there is a road from city X to Y? Output the shortest distance from X to Y. If not, output "Sorry". Sample Input
Sample Output
Source  
