复制粘贴图

时间限制：2s
空间限制：1024MB

题目描述

给定一个 $N\times N$ 的 01 矩阵 $A$。把 $A$ 在纵向和横向各复制排列 $K$ 次，得到 $NK\times NK$ 的矩阵 $X$；若 $X_{i,j}=1$，就在有向图中连边 $i\to j$。回答 $Q$ 次询问：顶点 $s$ 到顶点 $t$ 的最短路径长度是多少，不可达则输出 $-1$。

输入格式

第一行 $N,K$，随后 $N$ 行给出矩阵 $A$。下一行是 $Q$，再接 $Q$ 行，每行两个整数 $s,t$。

输出格式

对每个询问输出一行答案。

样例输入 1

3 2
1 1 1
1 1 0
0 1 0
4
1 2
1 4
1 6
6 3

样例输出 1

1
1
1
3

数据范围

对于所有数据，$1\le N\le100$，$1\le K\le10^9$，$1\le Q\le100$，$1\le s_i,t_i\le NK$ 且 $s_i\ne t_i$。