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(1-based).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

3 2

1 1

2 2

1 1

1 1

2 2

4 4

1

1 3

3 2

1 1

2 2

1 1

1 1

2 2

4 3

1

1 3

0 0

Sample Output

1 Sorry

分析： 如果用普通的乘法 很容易超时 可以把二维矩阵转化为一维矩阵。

#include
        
          #include
         
           #define clr(x)memset(x,0,sizeof(x)) #define inf 0x1f1f1f1f int dis[82][82]; int mat[82][82][82]; int mac[82][82]; int n,m; int ok(int c) {
      int i; for(i=1;i<=m;i++) if(mac[0][i]!=mac[c][i]) return 0; return 1;        } void mul(int a,int b) {
      int i,j; for(i=1;i<=m;i++)     {
              mac[0][i]=0; for(j=1;j<=m;j++)             mac[0][i]+=mat[a][i][j]*mac[b][j];     } for(i=1;i<=n;i++)     {
      if(i==a||i==b)continue; if(ok(i))             dis[a][i]=1;     } } int main() {
      int i,j,k,p,q,len; while(scanf("%d%d",&n,&m)&&(n&&m))     {
              memset(dis,inf,sizeof(dis)); for(i=1;i<=n;i++) for(j=1;j<=m;j++)             {
                      mac[i][j]=0; for(k=1;k<=m;k++)                 {
                          scanf("%d",&mat[i][j][k]);                     mac[i][j]+=mat[i][j][k]*k;                 }             } for(i=1;i<=n;i++) for(j=1;j<=n;j++)             {
      if(j==i)continue;                 mul(i,j);             } for(k=1;k<=n;k++) for(i=1;i<=n;i++)             {
      if(dis[i][k]!=inf) for(j=1;j<=n;j++) if(dis[i][k]+dis[k][j]