AT_arc159_a [ARC159A] Copy and Paste Graph

给定一个 $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 \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 翻译