题目描述

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

我们有以下有向图。

• 该图有 $NK$ 个顶点，编号为 $1,2,\ldots,NK$。
• 边对应于将 $K^2$ 个 $A$ 的副本按照 $K$ 行和 $K$ 列排列得到的 $NK$ × $NK$ 矩阵 $X=(x_{i,j})$（参见示例输入/输出 1）。
  • 如果 $x_{i,j}=1$，则从顶点 $i$ 到顶点 $j$ 有一条有向边；如果 $x_{i,j}=0$，则该边不存在。

对于 $i=1,2,\ldots,Q$，回答以下问题。

• 找到从顶点 $s_i$ 到顶点 $t_i$ 的最短路径长度（边的数量）。如果不存在这样的路径，输出 -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$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入中给出：

$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
1
3

以下是表示边的矩阵 $X$。

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

示例输入2

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

示例输出2

-1

没有边存在。