← 返回题目列表

AtCoder · arc159_a

A. 复制并粘贴图表

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

你被给予 N-by-N 矩阵 A=(a_{i,j}),其中 a_{i,j} \in \{0,1\}.

我们有以下有向图。

  • 该图有 NK 顶点编号 1,2,\ldots,NK.
  • 边缘对应于 NK-by-NK 矩阵 X=(x_{i,j}) 通过排列获得 K^2 副本 A in K 行和 K 列(有关示例,请参阅示例输入/输出 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

没有边缘。