题目描述

给定一个 $N$ 行 $N$ 列的矩阵 $A=(a_{i,j})$，其中 $a_{i,j} \in \{0,1\}$。

此外，存在如下的有向图：

• 顶点数为 $NK$，每个顶点编号为 $1,2,\ldots,NK$。
• 边由将 $A$ 纵向复制 $K$ 行、横向复制 $K$ 列得到的 $NK$ 行 $NK$ 列的矩阵 $X=(x_{i,j})$ 表示（在输入输出样例1中，给出了与 $A,\ K$ 对应的 $X$）。具体来说，若 $x_{i,j}=1$，则存在一条从顶点 $i$ 到顶点 $j$ 的有向边；若 $x_{i,j}=0$，则不存在这样的边。

对于 $i=1,2,\ldots,Q$，请回答下列问题：

• 求从顶点 $s_i$ 到顶点 $t_i$ 的最短路径长度（即边的数量的最小值）。如果不存在这样的路径，则输出 $-1$。

输入格式

输入以如下格式从标准输入读入。

$N$ $K$ $a_{1,1}$ $\ldots$ $a_{1,N}$
$\vdots$
$a_{N,1}$ $\ldots$ $a_{N,N}$
$Q$
$s_1$ $t_1$
$\vdots$
$s_Q$ $t_Q$

输出格式

输出 $Q$ 行。第 $x$ 行输出对应 $i=x$ 的问题的答案。

样例 1

输入

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

输出

1
1
1
3

样例 2

输入

4 1000000000
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1
1 4000000000

输出

-1

说明/提示

限制条件

• $1 \leq N \leq 100$
• $1 \leq K \leq 10^9$
• $a_{i,j} \in \{0,1\}$
• $1 \leq Q \leq 100$
• $1 \leq s_i, t_i \leq NK$
• $s_i \neq t_i$
• 所有输入均为整数

样例解释 1

在本例中，表示边的矩阵 $X$ 如下所示。

1 1 1 1 1 1
1 1 0 0 1 0
1 0 1 0 1 0
1 1 1 1 1 1
1 1 0 0 1 0
1 0 1 0 1 0

样例解释 2

不存在任何一条边。

由 ChatGPT 4.1 翻译